Dlaczego nie używamy większych klas do badania determinizmu kontra niedeterminizmu?

W poprzednim pytaniu dotyczącym hierarchii czasu dowiedziałem się, że równości między dwiema klasami mogą być propagowane do bardziej złożonych klas, a nierówności mogą być propagowane do mniej złożonych klas, z argumentami wykorzystującymi wypełnianie.

Dlatego przychodzi mi na myśl pytanie. Dlaczego badamy pytanie dotyczące różnych rodzajów obliczeń (lub zasobów) w najmniejszej możliwej (zamkniętej) klasie?

Większość badaczy uważa, że . To rozróżnienie klas nie byłoby pomiędzy klasami, które korzystają z tego samego rodzaju zasobów. Dlatego można uznać tę nierówność za uniwersalną zasadę: niedeterminizm jest silniejszym zasobem. Dlatego, choć nierówność, można ją propagować w górę, wykorzystując odmienną naturę dwóch zasobów. Można więc oczekiwać, że również. Jeśli ktoś udowodnił ten związek lub innych podobnych nierówności, to przekłada się na . $P \neq NP$ $EXP \neq NEXP$ $P \neq NP$

Mój argument może być jasny w zakresie fizyki. Newton miałby trudności ze zrozumieniem powszechnej grawitacji, badając skały (jabłka?) Zamiast ciał niebieskich. Większy obiekt oferuje więcej szczegółów w swoich badaniach, dając dokładniejszy model jego zachowania i umożliwiając ignorowanie zjawisk na małą skalę, które mogą być nieistotne.

Oczywiście istnieje ryzyko, że w większych obiektach zachowuje się inaczej, w naszym przypadku dodatkowa moc niedeterminizmu nie byłaby wystarczająca w większych klasach. Co jeśli w końcu zostanie udowodnione? Powinniśmy rozpocząć pracę nad następny dzień? $P \neq NP$ $EXP \neq NEXP$

Czy uważasz to podejście za problematyczne? Czy znasz badania, w których do rozróżnienia dwóch rodzajów obliczeń wykorzystuje się klasy większe niż wielomianowe?

cc.complexity-theory big-picture chazisop
źródło

Myślę, że te same bariery, które utrudniają udowodnienie P! = NP, utrudniają także oddzielenie EXP i NEXP. Na przykład uważam, że dla EXP i NEXP istnieje wynik braku relatywizacji. Jestem pewien, że ludzie rozważali pytania o separację dotyczące większych klas złożoności, ale wyobrażam sobie, że nie doprowadziło to do większego postępu niż próba oddzielenia mniejszych.

Philip White,

Właśnie przeczytałem kilka ostatnich akapitów; Mogłem źle odczytać twoje pytanie. Pytasz: „dlaczego nie możemy oddzielić P! = NP, badając podobne przypuszczenia, takie jak EXP! = NEXP?” czy pytasz: „dlaczego P? = NP wybrano zamiast innego pytania w celu zbadania różnic między determinizmem a niedeterminizmem?” Zakładam, że wiesz, że P = NP -> EXPTIME = NEXPTIME. Wydaje mi się, że odpowiedź na drugie pytanie wiąże się z faktem, że P jest wykonalne, podczas gdy EXPTIME nie. Ponadto NP ma znaczenie dla kryptografii. Myślę, że P? = NP wydaje się po prostu bardziej „odpowiedni”.

Philip White,

Drugie pytanie jest moim głównym pytaniem. Jednak pierwsze pytanie jest także powiązane: czy możemy raz na zawsze oddzielić niedeterminizm od determinizmu, czy też jesteśmy skazani na próbę rozwiązania nieskończonych pytań P! = NP, za każdym razem z większymi klasami? Argumentuję również, że chociaż P i NP są istotne dla naszych „ludzkich” problemów, być może potrzebne są większe klasy, które są nieosiągalne, aby zrozumieć siłę niedeterminizmu

chazisop,

Odpowiedzi:

Problem może być nieco czystszy z i . Najłatwiejszym sposobem myślenia o tych klasach jest to, że są one takie same jak i ale są ograniczone do języków jednoargumentowych . Oznacza to, że wszystkie dane wejściowe mają postać . $E=Dtime(2^{O(n)})$ $NE=Ntime(2^{O(n)})$ $P$ $NP$ $1^k$

Oznacza to, że język jest , wtedy i tylko wtedy, gdy język jest (Identyfikacja ciągi liczb z wykorzystaniem reprezentacji binarnej), i podobnie jest izomorficzny jednoargumentowy . $L$ $E$ $U_L = \{ 1^x : x\in L \}$ $P$ $NE$ $NP$

Tak więc, starając się oddzielić z jest jak nie próbuje po prostu osobnym z , ale rzeczywiście to zrobić za pomocą języka jednoargumentowy. Bez powodu powinno to uczynić twoje życie jeszcze łatwiejszym koncepcyjnie. $NE$ $E$ $P$ $NP$

Boaz Barak
źródło

To wydaje się wyjaśniać sytuację. Można więc powiedzieć, że

oznacza, że nie ma ogólnego algorytmu, który pozwalałby na wielomianową symulację NTM przez DTM, podczas gdy podobne instrukcje dla większych klas implikują tę samą instrukcję, ale dla bardziej specyficznych języków?

P \neq N P

$P \neq NP$

chazisop

Tak, rzeczywiście tak jest (dla bardziej ograniczonych rodzin języków)

Boaz Barak,

Dlaczego decydujemy się dbać o vs. ? W rzeczywistości niedeterminizm jako przedmiot badań ma drugorzędne znaczenie. Naprawdę dbają o ze względu na tysiące ważnych problemów , które są -Complete. Są to problemy, które chcemy (iw rzeczywistości musimy rozwiązać). Dbamy o to, czy problemy te można skutecznie rozwiązać, a jest naszym teoretycznym modelem wydajnego obliczania. W związku z tym, że prowadzi się do kwestii vs . $P$ $NP$ $NP$ $NP$ $P$ $P$ $NP$

Kristoffer Arnsfelt Hansen
źródło

Należy zauważyć, że znane są separacji niektórych nieograniczonych klas złożoności np , a także równości jak i $decidable \neq computability \ enumerable$ $NPSpace = PSpace$ $primitive \ recursive = nondeterministic \ primitive \ recursive$ . (Pouczające jest myśleć o tym, dlaczego trywialna wyściółka używanie ich nie jest pomocne dla rozstrzygnięcia P vs NP.) Powinniśmy być bardziej ostrożni, co rozumiemy przez takie pytanie vs i vs . Jeśli vs jest jego wyściełaną wersją (np. vs i vs ), odpowiedź Boaza również będzie miała zastosowanie. $P$ $NP$ $EXP$ $NEXP$ $P$ $NP$ $EXP$ $NEXP$ $E$ $NE$

Dowody na są znacznie słabsze niż i mają mniej dramatyczne konsekwencje, a są ludzie, dla których prawdopodobne, więc sytuacja jest tam bardziej skomplikowana i mamy znacznie słabsza intuicja dotycząca oczekiwanej odpowiedzi. Równość nie pomoże w praktyce i nie wiadomo, że ma wpływ na naprawdę interesujący przypadek, jakim jest vs , a nierówność jest formalnie i koncepcyjnie tak trudna jak nierówność między $EXP \neq NEXP$ $P \neq NP$ $EXP = NEXP$ $P$ $NP$ vs . $P$ $NP$

Kaveh
źródło

oznacza

, więc nie rozumiem twojego twierdzenia, że dowody na

są znacznie słabsze. Zauważ, że

implikuje, że

jest bardzo zaskakującym wynikiem.

E X P \neq N E X P

$EXP \ne NEXP$

P \neq N P

$P \ne NP$

E X P \neq N E X P

$EXP \ne NEXP$

E X P = N E X P

$EXP = NEXP$

N E X P = c o - N E X P

$NEXP = co-NEXP$

Mohammad Al-Turkistany

@turkistany: Dzięki za komentarz (choć nie uważam tego za dobry powód do głosowania w dół). Myślałem, że to oczywiste,

implikuje

ale nie vice versa, więc dowodem na

nie wydaje się być dowodem na

. W każdym razie

byłoby znacznie mniej zaskakujące niż

E X P \neq N E X P

$EXP \neq NEXP$

P \neq N P

$P \neq NP$

P \neq N P

$P \neq NP$

E X P \neq N E X P

$EXP \neq NEXP$

E X P = N E X P

$EXP=NEXP$

P = N P

$P=NP$ nie zgadzasz się

Kaveh

@Kaveh, pozwól mi się nie zgodzić. Znaleźć

jest bardzo zaskakujący wynik, gdyż oznacza to,

jak podano powyżej.

E X P = N E X P

$EXP = NEXP$

N E X P = c o - N E X P

$NEXP =co-NEXP$

Mohammad Al-Turkistany

@turkistany: Jest dla mnie jasne, że

byłoby znacznie bardziej zaskakujące niż

, ale jasne , że można się z tym nie zgodzić. :)

P = N P

$P = NP$

E X P = N E X P

$EXP=NEXP$

Kaveh

Jak definiujesz niedeterministyczną prymitywną rekurencyjną?

slimton