„Naturalne” rozstrzygalne problemy, o których wiadomo, że nie występują w NP.

13

Za każdym razem, gdy uczę kompletności NP, uczniowie pytają „czy są jakieś problemy, o których wiadomo, że nie należą do NP?”

Jak byś odpowiedział? Zazwyczaj daję im nierozstrzygalny problem jako przykład, ale często nie wychodzi to dobrze: (a) jeśli daję im problem z zatrzymaniem, myślą, że to jakiś głupi przypadek, i (b) jeśli dam im równania diofantyczne, nie rozumiem, dlaczego nie ma go w NP (możesz sprawdzić rozwiązania w czasie wieloczasowym ... po prostu je podłącz! Mam trudności z dezaktywacją ich w tym podejściu.)

Jako przykład chciałbym podać im coś w rodzaju QBF, ale nie ma udowodnionego podziału.

Propozycje?

cc.complexity-theory complexity-classes teaching Fixee
źródło

1

czy powinno to być CW? to duża lista ...

Suresh Venkat,

@Suresh, To zależy od twojego pojęcia naturalnego. Powinno być krótkie, jeśli ograniczymy się do „naturalnego” wystarczająco dla studentów.

Mohammad Al-Turkistany

2

Gra Go jest ukończona w PSPACE. Gra życia Conwaya jest nierozstrzygalna (tj. Odpowiednik maszyny Turinga) ... czy tego typu przykłady chciałeś?

user834

1

Zdecydowanie, czy ruch jest optymalny na szachownicy jest .

n X n

$n X n$

E X P T I M E - c o m p l e t e

$EXPTIME-complete$

chazisop

2

@chazisop nie wiadomo, czy poprawnie zawiera .

E X P T I M E

$EXPTIME$

N P

$NP$

Mark Reitblatt,

13

Jedną z możliwości jest problem z funkcją EXPSPACE. NP jest trywialnie w PSPACE, który jest ściśle zawarty w EXPSPACE. Jednym z problemów zakończonych EXPSPACE jest decyzja, czy wyrażenie regularne, które umożliwia potęgowanie, to całe $\Sigma^*$ .

Suresh Venkat
źródło

Co oznacza twoja notacja ?

L (R ↑) = L (R \cdot R \dots R)

$L(R\uparrow) = L(R\cdot R\ldots R)$

Neel Krishnaswami,

Uogólnia kwadratowanie (pobranie dokładnie dwóch kopii). Należy pamiętać, że zamknięcie Kleene ma dowolnie wiele kopii

Suresh Venkat

1

Czyli to samo co ? A może nieskończone powtórzenia?

L (R ↑) = ⋃_{n \in N} L (R^{n})

$L(R\uparrow) = \bigcup_{n \in \mathbb{N}} L(R^n)$

Neel Krishnaswami,

Nie sądzę, że nieskończone powtórzenia są uwzględnione.

Suresh Venkat

Dzięki i przepraszam za okropną pedanterię. Użycie jest zwykle jasne w kontekście, ale nie miałem żadnego. :)

\dots

$\ldots$

Neel Krishnaswami,

11

Skoro nacisk na naturalne problemy, oto bardzo naturalny problem z który nie występuje w : Problem z kwadratowymi kafelkami: Biorąc pod uwagę zestaw skończonych kafelków, czy kafelek ma kwadrat o rozmiarze x ? $NEXP$ $NP$ $2^n$ $2^n$

Zauważ, że gdy rozmiar kwadratu wynosi x ( jest zakodowany jako unarny), problem staje się . $n$ $n$ $n$ $NP$

Aby kwadratowych kafelków, sprawdź odnośnik. $NEXP$

[1] Christos H. Papadimitriou. Złożoność obliczeniowa. Addison-Wesley, Reading, Massachusetts, 1994

Mohammad Al-Turkistany
źródło

Fascynujący. Zatem ułożenie kwadratu o rozmiarze , gdzie jest reprezentowane w jednostkowej, jest NP-zupełne; i kafelkowanie kwadratu , gdzie jest reprezentowane w postaci binarnej, jest NEXP-complete. Czy to jest pomysł? Czy jest coś znanego na temat złożoności układania kwadratu, gdzie jest reprezentowane w postaci binarnej? A może miałeś na myśli, że jest reprezentowane w jedności nawet przez pierwsze zdanie twojej odpowiedzi?

n \times n

$n\times n$

n

$n$

2^{n} \times 2^{n}

$2^n\times 2^n$

n

$n$

n \times n

$n\times n$

n

$n$

n

$n$

DW

Tak na twoje ostatnie pytanie.

Mohammad Al-Turkistany

Układanie kwadratu kończy NEXP, gdy jest reprezentowane w postaci binarnej.

n \times n

$n \times n$

n

$n$

Mohammad Al-Turkistany

10

Jakikolwiek problem ukończony dla lub 2 jest znany z tego, że nie występuje w (według twierdzenia o hierarchii czasu). Podobnie dla $NEXPTIME$ $EXPTIME$ $NP$ $NEXPSPACE$ $EXPSPACE$

EXPSPACE:
Równoważność wyrażeń regularnych z operatorem potęgowania

2-WYŁĄCZENIE:
Zadowolenie dla CTL * (logika czasowa)
Zadowolenie dla ATL *
Problem decyzyjny dla arytmetyki Presburger

Mark Reitblatt
źródło

3

Rozróżnia się również arytmetykę Skolema, która jest arytmetyką z mnożeniem, ale bez dodawania. Fakt, że możesz zdecydować o teorii pierwszego rzędu jednego, ale nie zarówno dodawania, jak i mnożenia, wydaje mi się dość ważnym faktem.

Neel Krishnaswami,

5

Prostym przykładem jest funkcja tetracji , której nie ma nawet w ELEMENTARY . Możesz użyć wersji decyzyjnej tego.

Aaron Sterling
źródło

4

$g(n)$ $f(n+1) = o(g(n))$

$\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n))$

Na przykład żadnego problemu pełnego NEXP nie ma w NP. Cytowanie z Wikipedii :

Ważny zestaw problemów uzupełniających NEXPTIME dotyczy zwięzłych obwodów. Zwięzłe obwody to proste maszyny do opisywania wykresów w wykładniczo mniejszej przestrzeni. Akceptują dwie liczby wierzchołków jako dane wejściowe i wyjściowe, niezależnie od tego, czy istnieje między nimi krawędź. Jeśli rozwiązanie problemu na wykresie w naturalnej reprezentacji, takiej jak macierz przylegania, jest NP-zupełne, wówczas rozwiązanie tego samego problemu na zwięzłej reprezentacji obwodu jest NEXPTIME-complete, ponieważ dane wejściowe są wykładniczo mniejsze. Jednym prostym przykładem jest znalezienie ścieżki Hamiltona dla tak zakodowanego wykresu NEXPTIME-complete.

Zobacz także sekcję „Zwięzłe problemy” na stronie 492 książki Papadimitriou .

MS Dousti
źródło

2

Powiązane: cstheory.stackexchange.com/questions/3297/…

arnab

2

System kanałów to zestaw skończonych automatów z kanałami komunikacyjnymi, za pomocą których mogą wysyłać wiadomości. Wiadomość to litera alfabetu. W systemie z kanałami stratnymi wiadomości mogą być usuwane: list przesłany przez kanał może zniknąć. Problem osiągalności systemów z kanałami stratnymi jest rozstrzygalny, ale nieprymitywny rekurencyjny.

Dla delikatniejszego przykładu problem z osiągalnością systemów dodawania wektorów jest trudny w EXPSpace.

Vijay D.
źródło

„Naturalne” rozstrzygalne problemy, o których wiadomo, że nie występują w NP.

Odpowiedzi: