Problemy z NEXP-complete

Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem o tych rzeczach).

W idealnym przypadku lista powinna obejmować różne „rodzaje” problemów związanych z NEXP, być może z pewną zdrową redundancją, aby uzyskać ogólny obraz, ale bez powtarzania się zbyt wiele. Na przykład dobrze jest mieć dwie lub trzy różne zwięzłe wersje tego samego problemu NP-zupełnego jak przykłady, jeśli zwięzłe kodowanie występuje w nieco innych postaciach. Nie tuzin. Czystym sposobem na dodanie redundancji jest dodanie klauzul w postaci „Również NEXP-complete jeśli BLAH”. Mile widziane są również klauzule formularza „Pozostaje NEXP-complete, jeśli wykres wejściowy ma stopień co najwyżej BLAH”.

Na koniec pozwól mi dodać osobiste preferencje. Najbardziej interesują mnie kompletne problemy smaku „algebraicznego”, jeśli takie istnieją. Na przykład moim ulubionym problemem # P-zupełnym jest permanentny jego algebraiczny smak. Mam nadzieję, że równość NEXP = MIP może również dostarczyć fajnego algebraicznego problemu pełnego NEXP, którego nie jestem świadomy.

W przypadku niektórych problemów związanych z NP-zupełnością istnieje wariant SUCCINCT, który jest NEXP-complete.

Przykładem jest SUCCINCT HAMILTON PATH:

• Obwód boolowski z 2 n wejściami i jednym wyjściem reprezentuje wykres na 2 ⁿ wierzchołkach. Aby ustalić, czy istnieje krawędź między wierzchołkami i i j , zakoduj i i j w bitach n , i podaj ich konkatenację do obwodu: między tymi wierzchołkami jest krawędź, jeśli wyjście obwodu jest prawdziwe. Biorąc pod uwagę taki obwód, czy na wykresie jest ścieżka Hamiltona?

Podobnie istnieje SUCCINCT 3SAT, SUCCINCT KNAPSACK itp.

Odniesienie

• Hana Galperin i Avi Wigderson (1983), „Zwięzłe przedstawienie wykresów”, Information and Control 56: 3, s. 183–198.

Zobacz http://arxiv.org/abs/0905.2419 autorstwa Gottesman i Irani. To fajny przykład. Zasadniczo wszyscy jesteśmy przyzwyczajeni do idei, że spełnienie ograniczeń może być problemem NP-zupełnym (w zależności od geometrii itp.). Rozważają jednak sytuację, w której wszystkie ograniczenia są podane wcześniej i jedyną dozwoloną rzeczą jest różnić jest wielkość systemu. Jednak okazuje się to nadal trudne, jeśli zakodujesz problem w rozmiarze systemu. Oznacza to, że problem jest określony przez podanie ciągu N bitów, co daje rozmiar systemu od 0 do 2 ^ N-1. Tak więc rozmiar systemu jest wykładniczo większy niż rozmiar wejściowy. Pokazują, że jest to kompletny NEXP (i że analog kwantowy to kompletny QMA_EXP).

Zacznę od kanonicznego:

Biorąc pod uwagę niedeterministyczną maszynę Turinga i liczbę całkowitą zapisaną binarnie, czy istnieje ścieżka obliczeniowa która akceptuje pusty ciąg co najwyżej kroków?$M$$n$$M$$n$

Również NEXP-complete, jeśli jest napisane jednostronnie i prosimy o co najwyżej kroków.$n$$2^n$

Nierównoważność wyrażeń regularnych nad (union), (konkatenacja) i (kwadrat)$\cup$$\cdot$${}^2$ : czy biorąc pod uwagę dwa wyrażenia regularne, czy reprezentują one różne zestawy?

Wyrażenie regularne to albo

• $0$ ,
• $1$ ,
• $e\cup f$ ,
• $e\cdot f$ lub
• $e^2$ .

Te wyrażenia reprezentują zestawy

• $L(0)=\{0\}$ ,
• $L(1)=\{1\}$ ,
• $L(e\cup f)=L(e)\cup L(f)$ ,
• $L(e\cdot f)=\{ab\mid a\in L(e), b\in L(f)\}$ i
• $L(e^2)=L(e\cdot e)$ ,

odpowiednio.

Zauważ, że jeśli pozwolimy, by gwiazda Kleene (zero lub więcej kopii wyrażenia) była czwartym operatorem (oprócz zjednoczenia, konkatenacji i kwadratu), wówczas problem rozpoznania, czy dwa wyrażenia regularne reprezentują różne języki, stanie się EXPSPACE-zupełny .

LJ Stockmeyer, AR Meyer, „ Problemy słowne wymagające czasu wykładniczego ”, 5 STOC, 1973.

SCHÖNFINKEL – BERNAYS SAT

• Formuła w logice pierwszego rzędu należy do formuł klasy Schönfinkel – Bernays, jeśli można ją wyrazić w postaci (przy czym nie zawiera kwantyfikatorów ani symboli funkcji). Czy w przypadku formuły Schönfinkel – Bernays ma model?$∃x_1 ∃x_2 \ldots ∀y_1 ∀y_2 \ldots φ$$φ$

Odniesienie

• HR Lewis (1980), „ Wyniki złożoności dla klas wzorów ilościowych ”, Journal of Computer and System Sciences 21, s. 317–353.