2-NEXPTIME-zupełne problemy

Mamy problem i znaleźliśmy algorytm, który wydaje się być 2-sekundowy.

Chciałbym znaleźć znane problemy z niepełnym czasem 2, aby znaleźć dolną granicę.

W literaturze znalazłem głównie dwa takie problemy:

czy PCP jako rozwiązanie o rozmiarze mniejszym niż $2^{2^n}$
i problem uprawy roli dla kwadratu wielkości $2^{2^n}$

Jednak nie byłem w stanie zakodować tych problemów w moich. Chciałbym więc poznać inne problemy z 2-NEXPTIME, po pierwsze, aby mieć więcej intuicji w tej klasie, a po drugie, w lepszym przypadku, udowodnić dolną granicę.

Nie podaję tutaj problemu celowo, aby mieć szeroki przegląd 2-NEXPTIME.

Dzięki

complexity-classes time-complexity complexity wece
źródło

Zawieranie rekurencyjnych programów Datalog w związkach zapytań łączonych (Chaudhuri / Vardi 1997). Powinny być również inne problemy z logiką lub bazą danych, które są kompletne 2NEXP, ale nie przychodzą mi do głowy żadne inne konkretne problemy.

András Salamon,

@ AndrásSalamon Dziękujemy za odpowiedź. Nie znalazłem referencji, którą wskazałeś. Wszystko, co znalazłem, to wcześniejszy artykuł autorów, który stwierdził, że ten problem jest kompletny z 2-EXP (a nie 2-NEXP). Czy coś mi umknęło?

wece

masz rację, źle zapamiętałem wynik: problem jest ukończony 2EXP.

András Salamon

Zawsze pisałbym to jako N2ExpTime, a nie 2NExpTime, ponieważ zarówno „2”, jak i „Exp” odnoszą się do wartości górnej granicy czasowej, a „N” odnosi się do modelu maszyny. Umieszczenie modelu maszyny na środku nie wydaje się naturalne.

mak

Czy ktoś może mi podać odniesienie do kompletności PCP na 2 NEXPTIME przy rozwiązaniu o długości mniejszej niż 2 ^ 2 ^ n, proszę?

Corto,

Odpowiedzi:

Oczywistym problemem N2Exp jest oczywiście problem akceptacji słów dla niedeterministycznych maszyn Turinga o ograniczonym czasie 2exp. Korzystanie z tego może być tak trudne / łatwe jak kafelkowanie 2exp, ponieważ symulacja takiego obliczenia maszyny Turinga w istocie wymaga również zdefiniowania podwójnie wykładniczej dużej siatki (2exp wiele konfiguracji taśm pamięci o długości 2exp każda), która jest następnie wypełniana w sposób niedeterministyczny. W praktyce pokazanie dolnych granic N2Exp często sprowadza się do zbudowania takiej siatki (i upewnienia się, że nie jest to drzewo lub coś innego o niewystarczającej strukturze). „N” (niedeterminizm) jest często nieodłączną częścią problemu i nie jest tak trudny do zdobycia, gdy masz wystarczająco dużą siatkę (jeśli nie, na początku można strzelić do 2exp).

Innym praktycznym problemem związanym z N2ExpTime jest rozumowanie w logice opisu ekspresyjnego (DL). W szczególności DL $\mathcal{SROIQ}$ który jest podstawą standardu W3C OWL 2 Web Ontology Language jest N2ExpTime-complete (Jewgienij Kazakow: RIQ i SROIQ są trudniejsze niż SHOIQ. KR 2008: 274-284). Teraz prawdopodobnie nie jest to problem, którego chcesz użyć w redukcjach, ponieważ definicja logiki jest nieco niewygodna ze względu na wiele funkcji. Rzeczywisty dowód dolnej granicy dla $\mathcal{SROIQ}$ zostało to również zrobione przez redukcję do kafelków 2-exp. Jednak w zależności od twojego problemu, podana konstrukcja $\mathcal{SROIQ}$ może być inspirujące, aby zobaczyć, jak stworzyć tak duże siatki.

Kafelek pokazuje również inny ogólny wzorzec: N2Exp naprawdę jest jak NP, wystarczy znaleźć sposób na bardzo efektywne kodowanie nawet większych problemów. Zasadniczo możesz spróbować skalować każdy problem NP. Powód, dla którego kafelkowanie jest fajne, polega na tym, że wystarczy skalować rozmiar siatki w tym przypadku (co jest raczej jednolite).

Z drugiej strony, jeśli twój problem jest prawdopodobnie tylko 2ExpTime-zupełny, to możesz uciec z wykładniczą naprzemiennie symulowaną maszyną przemienną Turinga. Jeśli masz problemy z budowaniem siatki 2exp, ale możesz dostać się do rozmiarów wykładniczych, warto spróbować.

mak
źródło