Komplexiteten och tillnärmningen av problemet med begränsningstillfredsställelse (CSP) har studerats aktivt under de senaste 20 åren. En ny version av CSP, löftet CSP (PCSP) nyligen har föreslagits, motiveras av öppna frågor om tillnärmningen av varianter av satisfiability och graf färg. PCSP utökar avsevärt standardbeslutet CSP. Komplexiteten av CSPs med en fast begränsning språk på en ändlig domän har nyligen varit helt klassificerad, i hög grad vägledd av algebraic tillvägagångssätt, som använder polymorphisms - högdimensionella symmetrier av lösningsutrymmen - för att analysera komplexiteten av problem. Motsvarande klassificering för PCSPs är vidöppen och innehåller några långvariga öppna frågor, såsom komplexiteten i ungefärlig graf färg, som specialfall. Det grundläggande algebraiska förhållningssättet till PCSP initierades av Brakensiek och Guruswami, och i detta papper utökar vi avsevärt det och lyfter det från betongegenskaper av polymorfismer till deras abstrakta egenskaper. Vi introducerar en ny klass av problem som kan ses som algebraiska versioner av (Gap) Label Cover problem, och visa att varje PCSP med en fast begränsning språk motsvarar ett problem i denna form. Detta gör att vi kan identifiera en "mått på symmetri" som är väl lämpad för att jämföra och relatera komplexiteten hos olika PCSPs via algebraisk metod. Vi visar hur vår teori kan tillämpas genom att förbättra state-of-the-art i ungefärlig graf färg: vi visar att för alla k ≥ 3, är det NP-hård att hitta en (2k − 1)-färgning av en given k-färgbar graf. • Teori om beräkning → Problem, minskningar och fullständighet.
Helt nyligen visade Bulín, Krokhin och Opršal att hitta en 5-färgning av en 3-färgbar graf, och mer allmänt, hitta en (2k − 1)-färgning av en k-färgbar graf för alla k ≥ 3, är NP-hård REF.
Algebraic approach to promise constraint satisfaction
{'venue': 'STOC 2019', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}