Najnowsze publikacje na temat NP? = Pytanie coNP

Interesuje mnie pytanie, czy NP jest równy coNP, czy nie. Byłbym wdzięczny za porady dotyczące dobrych publikacji do przeczytania na ten temat.

Dla przypomnienia, wiem, że to pytanie jest ściśle związane z pytaniem, czy P jest równe NP, czy nie (takie, że jeśli NP! = CoNP, to P! = NP).

Na zdrowie, Derek

NP równa się coNP tylko wtedy, gdy istnieją skutecznie weryfikowalne dowody niezadowolenia. Tj. Wtedy i tylko wtedy, gdy istnieje wielomianowa maszyna Turinga , która dała dowolną formułę SAT i ciąg wyprowadza wtedy i tylko wtedy, gdy jest niezadowalająca. Większość teoretyków uważa, że ​​nie ma tak skutecznych dowodów, ale udowodnienie, że nie istnieją, rozwiązałoby pytanie P vs NP. Poczyniono jednak postępy w zakresie wykazania, że ​​dowody typu ograniczonego muszą koniecznie mieć rozmiar wielobiegunowy. Jest to przedmiotem złożoności dowodu: patrz dokument założycielski Cooka i Reckhow, ankieta przeprowadzona przez Krajicka lub te$M$$\phi$$\pi$$M(\phi, \pi) = 1$$\phi$notatki z wykładu Razborowa.

Jak sugeruje odpowiedź @ Sasho, będziesz mieć więcej szczęścia, jeśli poszukasz równoważnego pytania o „istnienie systemu dowodu super-propozycyjnego” niż bezpośrednio „ vs. ". Jest to kluczowe zagadnienie złożoności dowodu zdania. Znaczna część tego obszaru dowodzi super-wielomianowych dolnych granic dla poszczególnych systemów dowodu (w klasycznych terminach teorii złożoności, co dowodzi, że niektóre szczególne niedeterministyczne algorytmy nie są w stanie rozwiązać problemów w czasie wielomianowym).c o N P c o N $\mathsf{NP}$$\mathsf{coNP}$$\mathsf{coNP}$

Sam Buss ma fajny niedawny artykuł, który jest czytelny dla ogółu odbiorców. Możesz to sprawdzić:

• Samuel Buss, „ W stronę NP-P poprzez dowód złożoności i wyszukiwania ”, APAL, 2012.

(nie zawsze wskazywano, że coNP NP P NP; tak, ponieważ P jest zamknięty w uzupełnieniu. nie widzę nawet Wikipedii, która obecnie wyraźnie to stwierdza.) nie słyszała o nawet starszej ankiecie, która koncentruje się na NP Pytanie coNP w szczególności, może być tak, że jest postrzegane jako przypuszczalnie ściśle powiązane lub „co najmniej tak trudne” jak P NP. kwestia ta jest poruszana w niektórych badaniach P w porównaniu z NP, a np. niektóre wzmianki o koNP w Allender 2009 [2]. jak dla ostatnich wyników w pobliżu / powiązanych spróbuj [1]:→ ≠ ? = ? $\neq$$\rightarrow$$\neq$$\stackrel{?}{=}$$\stackrel{?}{=}$

[1] Zestawy twarde NP są wykładniczo gęste, chyba że coNP ⊆ NP / poly , Harry Buhrman, John M. Hitchcock (2008)

[2] Raport o stanie pytania P vs NP Allender (2009)