Vi presenterar en ny teknik, inspirerad av noll-kunskap bevissystem, för att bevisa lägre gränser på approximering av det kromatiska antalet av en graf. För att illustrera denna teknik presenterar vi enkla minskningar från max-3-färgning och max-3-sats, visar att det är svårt att uppskatta det kromatiska antalet inom (N ), för vissa > 0. Vi tillämpar sedan vår teknik i samband med de probabilistiskt kontrollerbara bevisen för H astad, och visar att det är svårt att approximera det kromatiska talet till inom (N 1? ) för alla > 0, förutsatt att NP 6 ZPP. Här betecknar ZPP den klass av språk som kan decideras av en slumpmässig förväntad polynom-tid algoritm som inte gör några fel. Vårt resultat matchar (upp till låg order) det kända gapet för att approximera storleken på den största oberoende uppsättningen. Tidigare O(N ) luckor för approximering av kromatiskt tal (såsom de av Lund och Yannakakis, och av Furer) matchade inte gapet för oberoende uppsättning, och sträcker sig inte längre (N 1=2? )..............................................................................................
Feige och Kilian REF visade att det kromatiska antalet inte kan uppskattas inom V 1 ε för någon ε 0, om inte NP ZPP.
Zero Knowledge and the Chromatic Number
{'venue': 'Journal of Computer and System Sciences', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}