Czy istnieje jakiś znany problem NP-Complete (lub NP-Intermediate) w podliniowej niedeterministycznej przestrzeni?

9

Istnieje kilka problemów z NP-Complete (SAT, SUBSETSUMitd.) DSPACE(n). Co z przestrzeniami nieliniowymi?

Czy istnieje jakiś znany problem NP-Complete (lub NP-Intermediate) w podliniowej niedeterministycznej przestrzeni?

Abuzer Yakaryilmaz
źródło

Odpowiedzi:

14

Każdy problem ma taką wersję, po prostu ją PAD! Np. Język, który składa się z prawdziwej 3CNF o długości m, po której następuje m ^ 2 0, jest w DSPACE (sqrt (n)).

domotorp
źródło
Dziękuję Ci! Czy masz jakiś pomysł na temat przestrzeni pollogarytmicznej?
Abuzer Yakaryilmaz
1
po prostu włóż 3CNF za pomocą 2nzera?
Sasho Nikolov
2
@Sasho: Wtedy problem przestałby być NP-zupełny, możesz tylko PAD z liczbą zerową.
domotorp
1
@Abuzer: Sądzę, że przestrzeń z poliklogami sugerowałaby, że NP jest częścią DTIME [2polylog]. To jest otwarte i mało prawdopodobne.
domotorp
@domotorp: Tak, masz rację! Dziękuję Ci!
Abuzer Yakaryilmaz
11

Dla dowolnego języka w NP istnieje dowód, który można zweryfikować za pomocą O(logn)przestrzeń robocza. Trzeba tylko użyć tych samych pomysłów, które zostały wykorzystane do udowodnienia, że ​​SAT jestNP-kompletny. Z definicji, biorąc pod uwagęNP język Lwiemy, że istnieje maszyna Turinga M tak, że dla każdego xL istnieje y takie, że M(x,y)akceptuje. Możemy zbudować weryfikowalny dowód przestrzeni logicznejx pisząc y i tableau obliczeń z M na wejściu x,y. W przestrzeni logów łatwo jest zweryfikować, czy tableau opisuje prawidłowe obliczenia akceptująceM. Podobnie dla każdegoxL i jakikolwiek y, brak prawidłowego obliczenia M(x,y) akceptuje, więc weryfikator obszaru logów nie zaakceptuje żadnego obrazu.

Oczywiście to nie pokazujeNP=NL (ponieważ to by sugerowało NP=P). Powodem jest to, że weryfikator ma dwukierunkowy dostęp do dowodu (może przechodzić do przodu i do tyłu). Definicja weryfikatoraNL daje weryfikatorowi przestrzeni logicznej tylko jednokierunkowy dostęp do dowodu (po odczytaniu odrobiny dowodu i ruchu głowy w prawo nie może się poruszać w lewo).

Sasho Nikolov
źródło
Nie mam pomysłu! Masz na myśli weryfikację probabilistyczną? Jeśli tak, to faktycznie stała przestrzeń jest wystarczająca dla dowolnego języka w NP od tego czasuDSPACE(2n)IP(1). Czy masz na myśli redukcję przestrzeni logowej dowolnego języka w NP na SAT? Jestem naprawdę zdezorientowany!
Abuzer Yakaryilmaz
1
Pozwól, że spróbuję inny sposób: jeden standardowy sposób definiowania NPjest jak klasa języków, które mają deterministyczne weryfikatory czasu policy. Mówię, że równoważną definicją jest zdefiniowanieNPjako klasa języków, które mają deterministyczne weryfikatory przestrzeni logowej z dostępem do dowodu wielokrotnego odczytu. losowość nie jest konieczna.
Sasho Nikolov
4
Dziękuję Ci. Właściwie to wiedziałem :) Oznaczono niedeterministyczną klasę log-space opartą na twoich wyjaśnieniachNSPACEoff-line(log), i tak, NP=NSPACEoff-line(log). Co więcej,NL=NSPACEon-line(log). Pojęcia „off-line” i „on-line”, jak wskazałeś, reprezentują typy dostępu do danego dowodu. ODNIESIENIE: Sekcja 5.3.1 złożoności obliczeniowej autorstwa Odeda Goldreicha (2008).
Abuzer Yakaryilmaz