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

18

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 .

complexity-theory proof-techniques

— Dave Clarke
źródło

Jasne, że to nie jest łatwe i nikt nie może udzielić odpowiedzi na twoją ogólną część :-) Mam zbyt wiele problemów Wiem, że są NP, ale nie wiem, czy są NP-Complete czy nie (ani zbyt wielu innych ludzi).

16

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$

— Ryan Williams
źródło

1

Z pewnością wygląda na to, że ugryzłem więcej, niż mogę przeżuć, że tak powiem.

— Dave Clarke

11

Problem w nie jest zupełny, jeśli istnieją inne problemy w 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 takie, że . $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 , ponieważ . Jednakże, jeśli chciał pokazać, że problem nie jest -Complete, to nie zawsze jest wystarczające, aby pokazać, że jest w , ponieważ nie wiadomo, czy . $EXPTIME$ $P$ $P \subsetneq EXPTIME$ $NP$ $P$ $P = NP$

— Joe
źródło

3

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.

— Mohammad Al-Turkistany
źródło

3

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

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

W przypadku, , i . $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 twarde, pokazujemy, że należy on do klasy złożoności, która, jak się uważa, jest mniejsza niż . Na przykład, można pokazać, że w , wtedy być wykorzystany jako silny dowód na 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}$

— Kaveh
źródło