Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.
Zakładając, że (a nawet, że hierarchia wielomianowa nie zawala się na żadnym poziomie), jest znany jako prawda czy fałsz? Jakie dowody można przedstawić za i przeciw?
cc.complexity-theory
complexity-classes
advice-and-nonuniformity
p-vs-np
np-intermediate
Vanessa
źródło
źródło
Odpowiedzi:
Oto możliwa alternatywa dla argumentu wypełniającego, oparta na uogólnieniu twierdzenia Ladnera przez Schöninga. Aby zrozumieć argument, musisz mieć dostęp do tego dokumentu (który niestety będzie dla wielu za ścianą płatną):
Zastosujemy główne twierdzenie z tego artykułu dla i będących językami, a i będącymi klasami złożoności w następujący sposób:A 2 C 1 C 2A1 A2 C1 C2
Dla jasności udowodnimy, że implikuje .N P I ⊈ P / p o l yNP⊈P/poly NPI⊈P/poly
Zakładając, że mamy i . Oczywiste jest, że i są zamknięte w skończonych odmianach. Artykuł Schöninga zawiera dowód, że jest rekurencyjnie prezentowalny (dokładną definicję można znaleźć w artykule), a najtrudniejszą częścią argumentu jest udowodnienie, że jest rekurencyjnie prezentowalny.A 1 ∉ C 1 A 2 ∉ C 2 C 1 C 2 C 1 C 2NP⊈P/poly A1∉C1 A2∉C2 C1 C2 C1 C2
Zgodnie z tymi założeniami twierdzenie implikuje, że istnieje język który nie jest ani w ani w ; i biorąc pod uwagę, że , utrzymuje, że jest do redukcji Karpa do , a zatem . Ponieważ znajduje się w ale nie jest -kompletny, ani w , wynika z tego, że .C 1 C 2 A 1 ∈ P A A 2 A ∈ N P A N P N P N P ∩ P / p o l y N P I ⊈ P / p o l yA C1 C2 A1∈P A A2 A∈NP A NP NP NP∩P/poly NPI⊈P/poly
Pozostaje udowodnić, że można rekurencyjnie prezentować. Zasadniczo oznacza to, że istnieje wyraźny opis sekwencji deterministycznych maszyn Turinga które zatrzymują się na wszystkich wejściach i są takie, że . Jeśli w moim argumencie występuje błąd, prawdopodobnie jest on tutaj, a jeśli naprawdę chcesz użyć tego wyniku, zrób to ostrożnie. W każdym razie, poprzez dopasowywanie do wszystkich niedeterministycznych maszyn Turinga w czasie wielomianowym (które można symulować deterministycznie, ponieważ nie dbamy o czas działania każdegoM 1 , M 2 , … N P ∩ P / p o l y = { L ( M k ) : k = 1 , 2 , … } M k M k M kNP∩P/poly M1,M2,… NP∩P/poly={L(Mk):k=1,2,…} Mk ) i wszystkie wielomiany reprezentujące górne granice wielkości rodziny obwodów boolowskich dla danego języka, uważam, że nie jest trudno uzyskać wyliczenie, które działa. Zasadniczo, każdy może przetestować, czy odpowiadający mu NTM czasu wielomianowego zgadza się z pewną rodziną obwodów wielomianowych aż do długości ciągu wejściowego, który jest podany, przeszukując wszystkie możliwe obwody boolowskie. Jeśli istnieje zgoda, wyprowadza tak jak NTM, w przeciwnym razie odrzuca (iw rezultacie reprezentuje skończony język).Mk Mk
Podstawowa intuicja stojąca za argumentem (ukrytym w wyniku Schöninga) jest taka, że nigdy nie można mieć dwóch „ładnych” klas złożoności (tj. Tych z rekurencyjnymi prezentacjami), które są rozłączne i siedzą naprzeciwko siebie. „Topologia” złożonych klas nie pozwala na to: zawsze możesz poprawnie zbudować język między dwiema klasami, w jakiś sposób naprzemiennie między nimi dla bardzo długich odcinków długości wejściowych. Twierdzenie Ladnera pokazuje to dla i , a uogólnienie Schöninga pozwala zrobić to samo dla wielu innych klas.N P CP NPC
źródło
Chciałbym tylko zapisać pewną wersję argumentu wypełniającego, jak opisano w komentarzach. Nie rozumiem, dlaczego potrzebna jest luka. Chcemy pokazać, że jeśli NP nie jest zawarty w P / poli, to istnieje problem pośredniego NP nie zawarty w P / poli.
Istnieje funkcja nieograniczona taka że SAT nie ma obwodów o rozmiarze mniejszym niż , a zatem istnieje funkcja która jest nieograniczona, rośnie, a . Niech SAT 'oznacza język uzyskany przez wypełnienie ciągów SAT o długości od do . Następnie:n f ( n ) g g ( n ) = o ( f ( n ) ) n n g ( n )f nf(n) g g(n)=o(f(n)) n ng(n)
Edytować:
Wybór jest nieco skomplikowany. Jeśli jesteś zadowolony z umieszczenia SAT w obiecującej wersji NP, ten bit jest niepotrzebny.g
Zdefiniuj jako maksymalną liczbę całkowitą, tak aby nie było obwodu o rozmiarze dla długości łańcuchów dla SAT. Zdefiniuj za pomocą algorytmu, który oblicza dla i zatrzymuje się po czasie lub gdy , i zwraca podłogę pierwiastka kwadratowego z najwyższej wartości znalezionej w tym czasie . Zatem jest nieograniczone, a i można obliczyć w czasie . Zauważ teraz, że powyższe argumenty polegają tylko na tym, że SAT nie ma obwodów o rozmiarze dla nieskończenie wielun f ( n ) nf(n) nf(n) n f ( m ) m = 1 , 2 , … n m = n g ( n ) lim inf g ( n ) / f ( n ) = 0 g ( n ) n n f ( n ) ng(n) f(m) m=1,2,… n m=n g(n) lim infg(n)/f(n)=0 g(n) n nf(n) n .
Interesujące byłoby również zobaczyć dowód, wydmuchując dziury w SAT, jak w http://blog.computationalcomplexity.org/media/ladner.pdf . Bez wymogu NP jest to dość łatwe: istnieje sekwencja taka, że żaden rozmiar os obwodu wykrywa ciągów SAT o długości ; ogranicz SAT do ciągów o długości dla niektórych .( n k ) k n n 2 2 i in1<n2<… (nk)k n n22i i
źródło
(NPI P / poly) (P NP)⊈ ⟹ ≠
źródło