NEXPTIME
W teorii złożoności , NEXPTIME lub NEXP , to klasa złożoności, czyli zbiór problemów decyzyjnych .
Dokładniej, jest to zbiór problemów decyzyjnych, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie O (2 p (n) ) z pewnym wielomianem „p” (n) i nieograniczoną przestrzenią pamięci. Jest to zatem niedeterministyczna wersja EXPTIME .
Definicja
W zakresie NTIME klasę definiuje:
.
Nieruchomości
Zgodnie z twierdzeniem o hierarchii czasu (w) , klasa NP różni się od NEXPTIME (ale uwzględniona). Jeśli P = NP, to EXPTIME = NEXPTIME.
NEXPTIME-kompletny problem
Problem jest NEXPTIME-trudny, jeśli jakikolwiek problem NEXPTIME zostanie zredukowany do niego w czasie wielomianowym. Problem jest NEXPTIME-ukończony, jeśli jest w NEXPTIME i jeśli jest NEXPTIME-trudny.
NEXPTIME-kompletne problemy uzyskane dla zwięzłości
Możemy przekształcić problem NP-zupełny w problem NEXPTIME-zupełny, jeśli uczynimy wpis problemu bardziej zwięzłym. Na przykład problem znalezienia ścieżki Hamiltona na grafie reprezentowanym przez macierz sąsiedztwa jest NP-zupełny. Ten sam problem, w którym wykres jest zwięźle reprezentowany przez zwięzły obwód, jest NEXPTIME-complete. Reprezentujemy wykres z 2 b wierzchołkami ponumerowanymi 0, 1, ..., 2 b - 1 przez obwód logiczny z wejściami 2b i taki, że istnieje łuk od wierzchołka i do wierzchołka j, jeśli obwód boolowski akceptuje binarne reprezentacje liczby i oraz j. Zatem zwięzła wersja problemu ścieżki hamiltonowskiej jest przeformułowana w następujący sposób: przy danym obwodzie boolowskim C, czy wykres odpowiadający C zawiera ścieżkę hamiltonowską.
Kilka kwestii decyzyjnych w zwięzłej wersji jest NEXPTIME-kompletne:
- Maksymalne cięcie na wykresie reprezentowanym przez obwód logiczny
- 3SAT zwięzły
- Zwięzłe SAT
- SAT obwodu logicznego przedstawionego zwięźle
Logika pierwszego rzędu
Problem spełnialności klasy Schönfinkel-Bernays jest NEXPTIME-complete.
Gry
Decydowanie, czy formuły binarne kwantyfikowane zależnościami są prawdziwe, to NEXPTIME-complete. W rezultacie drużynowa wersja graczy z niedoskonałymi informacjami o ograniczonej logice jest również kompletna w NEXPTIME.
Uwagi i referencje
- (w) Klasa NEXP na Złożoność Zoo
- Artykuł oryginalny: Joel I. Seiferas, Michael J. Fischer i Albert R. Meyer, „ Separating Nondeterministic Time Complexity Classes ”, Journal of the ACM , tom. 25, n o 1,1978, s. 146-167
- Juris Hartmanis, Neil Immerman, Vivian Sewelson. Rzadkie zestawy w NP-P: EXPTIME versus NEXPTIME. Informacja i kontrola , tom 65, z. 2/3, s. 158–181. 1985. W Bibliotece Cyfrowej ACM
- Christos H. Papadimitriou i Mihalis Yannakakis , „ Uwaga na temat zwięzłych reprezentacji wykresów ”, „ Informacje i kontrola” , tom. 71,1 st grudzień 1986, s. 181-185 ( DOI 10.1016 / S0019-9958 (86) 80009-2 , przeczytane online , dostęp 18 października 2016 )
- (en) Christos Papadimitriou , Computational Complexity , Addison-Wesley ,1993( ISBN 978-0-201-53082-7 )
- Gary L. Peterson i John H. Reif , „Multiple-person alternation”, w Proceedings of 20th Annual Symposium on Foundations of Computer Science , IEEE Computer Society,29 października 1979, 348–363 s. ( DOI 10.1109/SFCS.1979.25 , przeczytaj online ).
- Robert Aubrey Hearn , Gry, łamigłówki i obliczenia (praca doktorska),1 st styczeń 2006( przeczytaj online ).