Czy NPI jest zawarty w P / poly?

29

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.NPP/polyPH=Σ2PNPNPI:=NP(NPCP)P/polyNPIP/polyNPNPCP/poly

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?NPP/polyNPIP/poly

Vanessa
źródło
5
więc „co by się stało, gdyby wszystkie problemy w NP były kompletne lub w P \ poly”? z jednej strony oznaczałoby to małe obwody do faktoringu
Sasho Nikolov,
1
ps: post byłby bardziej czytelny, jeśli przeliterujesz „it” w cytowanej części. Możesz również użyć zamiast \ mathsf {NP} \ not \ subseteq \ mathsf {P} jako twoje założenie. NPP/polyNPP
Kaveh
4
Czy argument dopełniający nie pokaże, że tak się nie stanie, chyba że NP P / poly?
Peter Shor,
3
@PeterShor: Prawdopodobnie jestem gęsty, ale jak dokładnie by to działało?
Vanessa,
8
@Squark: nie jesteś gęsty ... Nie opracowałem dokładnie, jak to będzie działać i myślę, że nieco źle podałem wynik. Ale oto mój podstawowy pomysł. Załóżmy, że problemów NP-zupełnych nie da się rozwiązać w podwykonawczym czasie i po poradach. Weź X problem z NP-zupełnością i uzupełnij go tak, aby najszybszy algorytm był ledwo podwykonawczy. Potem jest NPI, więc można go rozwiązać w P / poly. Oznacza to, że problem NP-zupełny X można rozwiązać w czasie tylko nieznacznie wolniej niż czas P / poli. Dzięki redukcji wielomianowej wszystkie problemy związane z NP-zupełnością można teraz rozwiązać nieco wolniej niż czas P / poli.
Peter Shor,

Odpowiedzi:

18

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ą):

Uwe Schöning. Jednolite podejście do uzyskiwania zestawów diagonalnych w klasach złożoności. Theoretical Computer Science 18 (1): 95-103, 1982.

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 2A1A2C1C2

  • PA1= (lub dowolny język w )P
  • A2=SAT
  • C1=NPC
  • C2=NPP/poly

Dla jasności udowodnimy, że implikuje .N P IP / p o l yNPP/polyNPIP/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 1C 1 A 2C 2 C 1 C 2 C 1 C 2NPP/polyA1C1A2C2C1C2C1C2

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 1P A A 2 A N P A N P N P N PP / p o l y N P IP / p o l yAC1C2A1PAA2ANPANPNPNPP/polyNPIP/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 PP / p o l y = { L ( M k ) : k = 1 , 2 , } M k M k M kNPP/polyM1,M2,NPP/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).MkMk

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 CPNPC

John Watrous
źródło
7
To jest link do publikacji Schöninga dostępnych online za darmo, w tym do tej, do której się odwołujesz: uni-ulm.de/in/theo/m/schoening/…
Alessandro Cosentino,
1
Wielkie dzięki za odpowiedź! Zabawne jest to, że znałem twierdzenie Shoeninga, ale z jakiegoś głupiego powodu uważałem, że nie ma ono zastosowania w tym przypadku. Przy okazji, tekst jest dostępny bezpłatnie nawet w sciencedirect
Vanessa
1
@Squark: Nie jest głupotą podejrzewać, że twierdzenie Schöninga nie ma zastosowania, biorąc pod uwagę, że P / poly obejmuje języki nierekurencyjne. Przypuszczam, że to szczęście, że możemy go przeciąć z NP i nadal uzyskać wynik.
John Watrous,
1
@JohnWatrous: Tak, właśnie dlatego byłem zdezorientowany
Vanessa
15

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 )fnf(n)gg(n)=o(f(n))nng(n)

  • SAT 'jest w NP (patrz poniżej!)
  • SAT 'nie jest w P / poly: biorąc pod uwagę obwody o rozmiarze dla SAT', otrzymujemy obwody o rozmiarze dla SAT, ale jest to mniej niż dla niektórych .n g ( n ) k n f ( n ) nnkng(n)knf(n)n
  • Nie ma redukcji P / poli z SAT do SAT ': załóżmy, że dla sprzeczności istnieją obwody o rozmiarze dla SAT, pozwalając na bramki SAT'. Odbiór na tyle duże, że i pozwolić . Każda bramka SAT 'w ma co najwyżej wejść. Usuwając wejścia dopełniania, możemy przyciąć bramki SAT 'w do bramki SAT z wejściami mniejszymi niż , które możemy symulować za pomocą - powstałe bramki SAT mają co najwyżej Wejścia . Powtarzając to i traktując , SAT miałby obwody mniej więcej wielkościn k N g ( CnnkNn>NCnnkCng(N)>2kn>NCnnkCn Cn nk/2CNO(nknk/2nk/4)O(n2k)nf(n)nCnnk/2CNO(nknk/2nk/4)O(n2k) która jest mniejsza niż dla niektórych .nf(n)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)nf ( 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,nm=ng(n)lim infg(n)/f(n)=0g(n)nnf(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)knn22ii

Colin McQuillan
źródło
1
Po zapoznaniu się z odpowiedzią @ JohnWatrous przypomniano mi dowód Impagliazza na twierdzenie Ladnera poprzez wypełnienie (por. Dodatek Downey i Fortnow „Uniformly Hard Languages”: cs.uchicago.edu/~fortnow/papers/uniform.pdf ). W rzeczywistości twój dowód jest w zasadzie dowodem Impagliazza na Ladnera, ale dostosowanym do tej sytuacji. Schludny!
Joshua Grochow
1
Wielkie dzięki za odpowiedź! Przepraszam, że go nie wybrałem, ale musiałem wybrać jeden, a argument Watrous był łatwiejszy do zrozumienia, ponieważ wykorzystał wynik, który już znałem. Jest to dość subiektywny sposób wyboru, ale nie mogłem nic lepszego. W każdym razie wspaniale jest mieć więcej niż jeden sposób na uzyskanie interesującego wyniku
Vanessa
1
@Squark: absolutnie - i założyłem również, że twierdzenie Schöninga nie miało zastosowania.
Colin McQuillan,
-13

(NPI P / poly) (P NP)

vzn
źródło
8
jest zarówno znany, jak i trywialny: jeśli P = NP, to . także to nie jest pytanie, pytanie jest odwrotnością tego, co napisałeś, i na ile, jak widzę, Colin przekonująco na nie odpowiedział. NPINP=PP/pol
Sasho Nikolov,
pytanie zatytułowane jest „czy NPI jest zawarte w P / Poly” i myślę, że jest to rozsądna odpowiedź, nie jestem pewien, czy jest naprawdę trywialna ze względu na sposób definiowania NPI (jako zależny od P NP) ... ta odpowiedź nie konflikt z drugą odpowiedzią ...
dniu
9
W rzeczywistości jest to jeszcze bardziej oczywiste: jeśli P = NP, NPI jest puste. Pytanie jest jasno określone jako „czy NP nie jest zawarty w P / poli oznacza, że ​​NPI nie w P / poli. Twoja odpowiedź 1) twierdzi, że trywialny fakt jest otwartym problemem 2) nie odnosi się do pytania
Sasho Nikolov
8
Nie obchodzi mnie mniej punktów. Po raz ostatni: mój pierwszy komentarz, odpowiedź Colina i samo pytanie związane są z mniej trywialną i bardziej interesującą konwersacją pustej implikacji, którą zapisałeś.
Sasho Nikolov,
11
-1: czasami utrata punktu wydaje się właściwa
Alessandro Cosentino,