Menunjukkan bahwa masalah dalam X bukanlah X-Complete

Teori Keberadaan Real ada di PSPACE , tapi saya tidak tahu apakah itu PSPACE-Complete . Jika saya percaya bukan itu masalahnya, bagaimana saya bisa membuktikannya?

Lebih umum, diberikan masalah dalam beberapa kompleksitas kelas X , bagaimana saya bisa menunjukkan bahwa itu bukan X-Lengkap ? Misalnya, X bisa NP , PSPACE , EXPTIME .

Sebenarnya membuktikan bukan -complete (di bawah, katakanlah, pengurangan polinomial-waktu) akan sangat sulit dilakukan.$X$$PSPACE$

Jika , maka semua non-sepele (yaitu, bukan dan bukan ) dan masalah tak terbatas di adalah -complete di bawah pengurangan waktu polinomial. Karena teori eksistensial real memiliki properti non-sepele dan tak terbatas ini, membuktikan bahwa itu bukan -lengkap akan menyiratkan . (Lihat jawaban untuk pertanyaan ini di CSTheory.SE untuk sketsa buktinya.)∅ Σ ⋆ P S P A C $P=PSPACE$$\varnothing$$\Sigma^{\star}$$PSPACE$$PSPACE$ P ≠ P S P A C $PSPACE$$P \neq PSPACE$

Masalah dalam bukanlah X -complete jika ada masalah lain di X yang tidak bisa dikurangi. Salah satu metode sederhana (tapi mungkin hanya efektif pada contoh sepele) akan membuktikan masalah Anda juga di beberapa kelas kompleksitas lainnya Y sehingga Y ⊂ X .$X$$X$$X$$Y$$Y \subset X$

Misalnya, jika Anda ingin menunjukkan bahwa masalah Anda tidak lengkap, maka itu cukup untuk menunjukkan bahwa dalam P , karena P ⊊ E X P T I M E . Namun, jika Anda ingin menunjukkan bahwa masalah bukan N P -complete, maka itu tidak selalu cukup untuk menunjukkan bahwa itu ada di P , karena tidak diketahui apakah P = N P atau tidak .$EXPTIME$$P$$P \subsetneq EXPTIME$$NP$$P$$P = NP$

Lihatlah jawaban yang diterima untuk pertanyaan ini pada MathOverflow, Apa teknik yang ada untuk menunjukkan bahwa masalah tidak lengkap NP? . Ini menjawab kasus ketika X = NP.

Seperti yang ditulis Ryan, membuktikan bahwa masalah itu tidak sulit tidak mudah.

Biarkan menjadi masalah dalam kelas kompleksitas X dan S ditutup pengurangan ≤ . Membuktikan bahwa Q bukan X -hard wrt ≤ sama dengan memisahkan kelas kompleksitas yang diperoleh dengan mengambil penutupan Q wrt ≤ . Sekarang, jika Q sulit untuk kelas lain Y wrt ≤ , maka itu berarti memisahkan Y dari X . Seperti yang Anda ketahui, tidak ada banyak hasil pemisahan.$Q$$X$$S$$\leq$$Q$$X$$\leq$$Q$$\leq$$Q$$Y$$\leq$$Y$$X$

Dalam kasus Anda, , ≤ = ≤ P m , dan Y = P .$X = \mathsf{PSpace}$$\leq = \leq^\mathsf{P}_m$$Y=\mathsf{P}$

Karena kami tidak dapat membuktikan hasil seperti saat ini (dengan kemungkinan Ryan :), sebagai pengganti membuktikan bahwa bukan X-keras , kami menunjukkan bahwa itu berada dalam kelas kompleksitas yang diyakini lebih kecil dari X . Misalnya, jika Anda menunjukkan bahwa T h ∃ ( R , + , × , 0 , 1 ) adalah dalam P H , maka itu akan diambil sebagai bukti kuat untuk Q tidak menjadi $Q$$X$$X$$\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$$\mathsf{PH}$$Q$$X$-keras. (Dalam bahasa ahli logika, jika Anda tidak dapat membuktikan hasil tanpa syarat, coba buktikan yang bersyarat dengan asumsi yang sulit dibuktikan tetapi secara luas diyakini seperti ).$\mathsf{P}\neq\mathsf{PSpace}$