Problemy z NEXP-complete

31

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.

slimton
źródło
2
Wiki Wiki!
Dave Clarke
Jak zamienia się w wiki społeczności?
slimton
Oflaguj post, aby zwrócić uwagę moderatora i poproś go, aby uzyskał CW.
Kaveh
5
dlaczego NEXP? tj. dlaczego nie jakaś inna klasa?
Suresh Venkat
1
Zauważ, że klasa NEXP jest czasami nazywana również NEXPTIME. Może to ujawnić dodatkowe wyniki podczas korzystania z wyszukiwarek.
Hermann Gruber

Odpowiedzi:

26

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 n 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.
Gareth Rees
źródło
17

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).

matowe pośpiechy
źródło
15

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?MnMn

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

slimton
źródło
15

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

Wyrażenie regularne to albo

  • 0 ,
  • 1 ,
  • ef ,
  • ef lub
  • e2 .

Te wyrażenia reprezentują zestawy

  • L(0)={0} ,
  • L(1)={1} ,
  • L(ef)=L(e)L(f) ,
  • L(ef)={abaL(e),bL(f)} i
  • L(e2)=L(ee) ,

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.

Sadeq Dousti
źródło
14

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?x1x2y1y2φφ

Odniesienie

Gareth Rees
źródło
Czy odwrotna (niezadowalająca) zgodność coNEXP?
gigabajty
Zawsze myślałem, że formuła logiczna pierwszego rzędu φ bez kwantyfikatorów jest formułą logiczną. Czyż nie Ale dla wzoru logicznego φ byłoby to Σ ^ P_2 ukończone. Czy zmienne we wzorze Schönfinkela-Bernaya mogą mieć inne wartości niż prawda i fałsz?
BeniBela,
@BeniBela: Są to formuły logiki pierwszego rzędu, więc mogą zawierać symbole relacji (których znaczenie musi określić model). Zobacz referencję. Jeśli model jest ograniczony do dwóch elementów, mamy BINARY SCHÖNFINKEL – BERNAYS SAT, który pozostaje NEXP-complete . φ
Gareth Rees