Pokazuje, że problem w X nie jest X-Complete

Egzystencjalna teoria Real jest w PSPACE , ale nie wiem, czy to jest PSPACE zupełnych . Jeśli uważam, że tak nie jest, jak mogę to udowodnić?

Mówiąc bardziej ogólnie, biorąc pod uwagę problem z pewną klasą złożoności X , jak mogę pokazać, że nie jest to X-Complete ? Na przykład X może oznaczać NP , PSPACE , EXPTIME .

Faktycznie udowodnienie, że $X$ nie jest $PSPACE$ całkowite (przy, powiedzmy, redukcjach czasu wielomianowego) byłoby niezwykle trudne.

Jeśli $P=PSPACE$ , to wszystkie nietrywialne (tj. Nie $\varnothing$ i nie $\Sigma^{\star}$ ) i nieskończone problemy w $PSPACE$ są $PSPACE$ ukończone w ramach redukcji czasu wielomianowego. Ponieważ egzystencjalna teoria reali ma tę nietrywialną i nieskończoną właściwość, udowadnianie, że nie jest to $PSPACE$ oznaczałaby . (Zobaczodpowiedź na to pytanie w CSTheory.SE,aby uzyskać szkic dowodu).$P \neq PSPACE$

Problem w nie jest X- zupełny, jeśli istnieją inne problemy w X, których nie można do niego zredukować. Jedno proste (ale prawdopodobnie działa tylko na trywialne przykłady) metodą byłoby udowodnienie problem jest również w innej klasie złożoności Y takie, że Y ⊂ X .$X$$X$$X$$Y$$Y \subset X$

Na przykład, jeśli chcesz, aby pokazać, że problem nie jest kompletne, to wystarczy, aby pokazać, że jest w P , ponieważ P ⊊ E X P T I M E . Jednakże, jeśli chciał pokazać, że problem nie jest N P -Complete, to nie zawsze jest wystarczające, aby pokazać, że jest w P , ponieważ nie wiadomo, czy P = N P .$EXPTIME$$P$$P \subsetneq EXPTIME$$NP$$P$$P = NP$

Spójrz na zaakceptowaną odpowiedź na to pytanie dotyczące MathOverflow. Jakie techniki istnieją, aby pokazać, że problem nie jest NP-zupełny? . Odpowiada na przypadek, gdy X = NP.

Jak napisał Ryan, udowodnienie, że problem nie jest trudny, nie jest łatwe.

Niech będzie problemem w klasie złożoności X, a S jest zamknięte wrt ≤ redukcje. Udowodnienie, że Q nie jest X- twarde wrt ≤ jest równoważne oddzieleniu klasy złożoności uzyskanej przez zamknięcie Q wrt ≤ . Teraz, jeżeli Q jest trudne do innej klasy Y wrt ≤ , to znaczy, oddzielając Y od X . Jak wiadomo, wyników separacji jest niewiele.$Q$$X$$S$$\leq$$Q$$X$$\leq$$Q$$\leq$$Q$$Y$$\leq$$Y$$X$

W przypadku, , ≤ = ≤ P m i Y = P .$X = \mathsf{PSpace}$$\leq = \leq^\mathsf{P}_m$$Y=\mathsf{P}$

Ponieważ nie możemy obecnie udowodnić takich wyników (z możliwym wyjątkiem Ryana :), zamiast udowodnić, że nie jest X- twarde, pokazujemy, że należy on do klasy złożoności, która, jak się uważa, jest mniejsza niż X . Na przykład, można pokazać, że T H ∃ ( R , + , x , 0 , 1 ) w P H , wtedy być wykorzystany jako silny dowód na Q nie będącego $Q$$X$$X$$\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$$\mathsf{PH}$$Q$$X$-ciężko. (W języku logików, jeśli nie możesz udowodnić bezwarunkowego wyniku, spróbuj udowodnić warunkową, zakładając trudne do udowodnienia, ale powszechnie uważane stwierdzenie, takie jak ).$\mathsf{P}\neq\mathsf{PSpace}$