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ż
- i problem uprawy roli dla kwadratu wielkości
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
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 DLSROIQ 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 dlaSROIQ zostało to również zrobione przez redukcję do kafelków 2-exp. Jednak w zależności od twojego problemu, podana konstrukcjaSROIQ 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ć.
źródło