[Teoria złożoności] Bzdura w książce?

[diego_maradona]

Zatem pytanie, czy istnieją trudno rozwiązywalne problemy, które stają się łatwo rozwiązywalne dzięki wprowadzeniu równoległości, sprowadza się do pytania, czy sekwencyjna klasa złożoności PSPACE zawiera problemy trudno rozwiązywalne, tzn. takie, o których można udowodnić, że nie mają sekwencyjnych rozwiązań w czasie wielomianowym. To pytanie wyrażone wyłącznie w kategoriach sekwencyjności jest nadal otwarte i podobnie jak problem, czy P=NP, jest prawdopodobnie również bardzo trudne.

ISBN 83-204-2688-X , s 294

Kilka stron temu napisali, że NPTIME\(\displaystyle{ \subseteq}\) PSPACE, a teraz się zastanawiają, czy istnieje jakikolwiek problem NPTIME który jest jednocześnie PSPACE?

[norwimaj]

a teraz się zastanawiają, czy istnieje jakikolwiek problem NPTIME który jest jednocześnie PSPACE?

Nie, nie nad tym się zastanawiają. Co oznacza skrót NPTIME?

[diego_maradona]

Z tego co zrozumiałem oznacze tyle, że problem decyzyjny jest rozwiązywalny w czasie wielomianowym jeśli mamy do dyspozycji wyrocznię. Jako że takowej nie mamy i mieć nie będziemy to nigdy nie rozwiążemy takiego problemu w czasie wielomianowym lub niższym.

[norwimaj]

Jako że takowej nie mamy i mieć nie będziemy to nigdy nie roziążemy takiego problemu nawet w czasie wielomianowym.

W takim razie problem P=NP też jest kompletną bzdurą. Problemy w P są rozwiązywalne w czasie wielomianowym, a problemy w NP - jak twierdzisz - nie mogą być rozwiązane w czasie wielomianowym bo nie mamy wyroczni. Zatem zbiory P i NP są rozłączne, a ponieważ co najmniej jeden z nich jest niepusty, nie mogą być równe.

[diego_maradona]

Ok, jeśli chodzi o ścisłość to powinno być:

Jeśli NP != P, to bez użycia wyroczni nigdy nie rozwiążemy takiego problemu w czasie wielomianowym lub niższym.

Nawet jeśli teraz mam dobrą definicję NPTIME, to i tak nie rozumiem jak to się ma do pytania, skoro zbiór PSPACE zawiera NPTIME i PTIME bez względu na status problemu P=NP.

Poza tym

jak twierdzisz

nic nie stwierdzam, wszystko co napisałem w tym temacie to są moje przypuszczenia.

[_karolina_]

ewidentny błąd w książce/tłumaczeniu

[norwimaj]

W definicji NP nic nie jest powiedziane o tym, co się dzieje gdy nie mamy wyroczni. Być może wszystkie problemy z NP da się rozwiązać w czasie wielomianowym bez wyroczni (jeśli P=NP).

W cytowanym przez Ciebie fragmencie mowa jest albo o problemie, czy \(\displaystyle{ \text{PSPACE}\setminus \text{P}=\emptyset}\), albo czy \(\displaystyle{ \text{PSPACE}\setminus\text{NP}=\emptyset}\) (oczywiście kłamię, ale to dlatego że nie chcę zaciemniać sprawy).

[Zordon]

Na dzień dzisiejszy nikt nie potrafi wykluczyć, że zachodzi \(\displaystyle{ P=PSPACE}\), dlatego też ten fragment książki ma sens.

[diego_maradona]

No tak! Jeśli udowodnionoby, że P=NP, to klasa NP zostałaby wchłonięta przez klasę P i PSPACE nie zawierałoby ani jednego trudno rozwiązywalnego problemu. Fragment niby poprawny, ale fakt że nie wspomniano o ścisłej relacji między P=NP a pogrubionym przeze mnie pytaniem spowodował mocną dezorientację.

[norwimaj]

No tak! Jeśli udowodnionoby, że P=NP, to klasa NP zostałaby wchłonięta przez klasę P i PSPACE nie zawierałoby ani jednego trudno rozwiązywalnego problemu.

A nie może się okazać, że \(\displaystyle{ \text{P}=\text{NP}\varsubsetneq\text{PSPACE}}\)?

[diego_maradona]

A nie może się okazać, że \(\displaystyle{ \text{P}=\text{NP}\varsubsetneq\text{PSPACE}}\)?

Wikipedia mówi, że nie.

[Zordon]

Wikipedia nie mówi, że nie. Takiego scenariusza również nie potrafimy wykluczyć.

[diego_maradona]

@Zordon, wynika to z poprzedniego obrazka oraz z artykułu w którym on się znajduje:

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ NP ⊆ PP ⊆ PSPACE, but it is possible that P = PSPACE.

... ity_theory

[Zordon]

Nie wiem jakim cudem z tego zdania wnioskujesz, że nie jest możliwa sytuacja:
\(\displaystyle{ P=NP\varsubsetneq PSPACE}\).

Aha, mam pewne podejrzenie co do źródła nieporozumienia: znak \(\displaystyle{ \varsubsetneq}\) symbolizuje inkluzję bez równości, nie zaś brak inkluzji.

[diego_maradona]

Aha, mam pewne podejrzenie co do źródła nieporozumienia: znak varsubsetneq symbolizuje inkluzję bez równości, nie zaś brak inkluzji.

Ahh faktycznie. Wszystko przez to, że za moich czasów nie było takich cudacznych oznaczeń