Seberapa Keras Simulasi yang Tepat dari Algoritma, dan Operasi Terkait pada Kelas Kompleksitas

Penggoda

Karena masalahnya gondrong di sini adalah kasus khusus yang menangkap esensinya.

Masalah: Misalkan A menjadi algoritme detrministik untuk 3-SAT. Apakah masalah sepenuhnya mensimulasikan algoritma A (pada setiap contoh masalah). P-Space keras?

(Lebih tepatnya, apakah ada alasan untuk percaya bahwa tugas ini adalah P-Space keras, melakukan sesuatu dalam arah ini mengikuti dari dugaan CC standar, dan apakah ada harapan untuk membuktikan bahwa tugas ini adalah X-keras untuk beberapa kompleksitas kelas X yang dianggap benar-benar di atas NP.)

Pertanyaan terkait : apakah-pspace-complete-problems-inheren-kurang-traktable-daripada-np-complete-masalah ;

EDITED UPDATE : Ada berbagai interpretasi untuk "Sepenuhnya mensimulasikan A". Dan mungkin ada jawaban menarik yang berbeda sesuai dengan interpretasinya. (Juga Ryan Williams mengusulkan interpretasi untuk mensimulasikan algoritma non deterministik.) Untuk cara tertentu untuk mengaitkan masalah keputusan dengan tugas komputasi "Sepenuhnya mensimulasikan A", Joe Fitzsimons menemukan algoritma A yang masalah keputusan terkait ini masih dalam NP . Jika "benar-benar mensimulasikan" mengacu mampu output seluruh daftar komputer pada langkah tertentu $i$ maka untuk algoritma Joe tampaknya $P^{NP}$ adalah apa yang dibutuhkan. Untuk versi ini (saya pikir, tetapi tidak yakin) Jawaban Ryan membuat sketsa$P^{NP}$Argumen-kekerasan. Joe berkomentar bahwa jika Anda diminta untuk memasok seluruh register (yang bukan lagi masalah keputusan) itu tidak surpising bahwa Anda perlu meningkatkan dan kelas kompleksitas tidak sama.

Lagi pula, jika kita perlu menampilkan status register pada langkah yang ditentukan maka jawaban Ruan dan Joe menyarankan (tapi sekali lagi, saya tidak yakin tentang hal itu) bahwa pada dasarnya adalah . Kita dapat spaculate bahwa dengan interpretasi ini operasi mendorong satu langkah lebih tinggi dalam hiearachy polinomial, dan bahwaN P + P N $i$$NP^+$$P^{NP}$$PH^+ =PH$ .

Bagaimanapun dengan interpretasi ini jawaban untuk pertanyaan penggoda saya adalah TIDAK .

Saya memiliki interpretasi yang lebih drastis untuk "sepenuhnya mensimulasikan algoritma A" dalam pikiran. (Tapi mungkin interpretasi Joe dan Ryan lebih menarik.) Interpretasi saya dengan "sepenuhnya simulasi algoritma A" adalah bahwa Anda melampaui status register pada setiap langkah . Khususnya, jika algoritma tidak polinomial, output Anda juga tidak polinomial. Di bawah interpretasi drastis ini saya bertanya-tanya apakah kita harus percaya bahwa untuk setiap algoritma A, C A adalah P-SPACE sulit, dan apa yang bisa kita buktikan.$i$$C_A$

Motivasi:

Pertanyaan ini dimotivasi oleh ceramah oleh Paul Goldberg ( slide , video , kertas ) yang menggambarkan sebuah makalah dengan Papadimitriou dan Savani. Mereka menunjukkan bahwa P-space lengkap untuk menemukan keseimbangan apa pun yang dihitung oleh algoritma Lemke-Howson. Masalah untuk menemukan beberapa titik keseimbangan hanya lengkap PPAD. Kesenjangan ini sangat menakjubkan dan hasil yang serupa dijelaskan di dalam makalah Papadimitriu yang terkenal: Kompleksitas Argumen Paritas dan Bukti Keberadaan Lainnya yang Tidak Efisien (1991) . (Diketahui bahwa masalah lengkap PPAD bahkan tidak bisa NP-keras (kecuali hal-hal buruk terjadi sehingga ini jauh di dunia kompleksitas dibandingkan dengan P-space).

Tentang apa pertanyaan itu

Pertanyaan saya adalah tentang kesenjangan yang sama untuk masalah kompleksitas komputasi yang lebih tua dan lebih klasik. (Mungkin ini sudah akrab.)

Mengingat masalah komputasi kita dapat membedakan antara tiga masalah

a) Memecahkan masalah secara algoritmik

b) Mencapai solusi yang sama dengan algoritma spesifik A

c) Mensimulasikan seluruh algoritma A

Tentu saja c) setidaknya sekeras b) yang setidaknya sekeras a). Hasil yang disebutkan di atas menunjukkan kesenjangan antara kesulitan komputasi dari tugas a) dan b) untuk masalah komputasi kesetimbangan. Kami ingin memahami situasi (dan terutama kesenjangan antara a) dan c)) untuk masalah komputasi lainnya.

Pertanyaan:

Bentuk dasar dari pertanyaan dengan contoh

Kami mulai dengan masalah komputasi, Masalah X

Contohnya bisa

Masalah X: Memecahkan instance SAT dengan n variabel

kami juga menentukan

A: sebuah algoritme yang menjalankan Masalah X

dan kami menimbulkan masalah baru

Masalah Y: Simulasi algoritma yang tepat A

dan kami tertarik pada kesulitan komputasi pada Masalah Y. Kami ingin memahami kelas masalah seperti Y untuk semua algoritma A yang menyelesaikan Masalah X asli. Terutama kami ingin tahu seberapa mudahnya masalah Y (atau seberapa sulit haruskah itu) menjadi) jika kita diizinkan untuk memilih algoritma A sesuka hati.

Usulan operasi pada kelas kompleksitas

Mulai dengan kelas kompleksitas yang dijelaskan oleh beberapa tugas komputasi. Mengingat algoritma A untuk melakukan setiap contoh tugas komputasi ini, mempertimbangkan kelas kompleksitas baru C A yang digambarkan oleh tugas komputasi completly simulasi A . Maka kita dapat (mudah-mudahan) mendefinisikan "ideal" kelas kompleksitas$C$$C_A$$A$

untuk semua algoritma A}.$C^+ = \{C_A:$

Jika kita membiarkan untuk menggambarkan apa pun yang dapat dilakukan komputer digital dalam waktu polinomial (jadi saya tidak ingin membatasi perhatian misalnya untuk masalah keputusan) maka P + adalah yang ideal yang direntang oleh P itu sendiri.$P$$P^+$$P$

Akhirnya, Pertanyaan Saya

Pertanyaan saya adalah:

1) Apakah definisi itu masuk akal (dalam arti luas dari kata akal). Apakah itu dikenal atau sama dengan (atau mirip dengan) beberapa hal yang diketahui. (Formulasi saya bersifat informal dan khususnya ketika kita beralih dari masalah khusus seperti SAT ke kelas kompleksitas seperti NP kita harus khawatir tentang berbagai hal yang saya abaikan.)

Dua pertanyaan berikutnya mengasumsikan bahwa definisi tersebut masuk akal atau diselamatkan masuk akal.

2) Misalkan kita melengkapi diri kita sendiri dengan semua dugaan standar tentang kepatuhan komputasi. Dapatkah kita mengatakan apa seharusnya untuk beberapa kelas kompleksitas akrab. (Misalnya C = N P , C = P-space, ..)? EDIT: Beberapa orang mengatakan bahwa P S P A C E + = P S P A C E . Jadi, kita bisa bertanya apa yang ada$C^+$$C=NP$$C$$PSPACE^+=PSPACE$ ? Apakah P H + = P H ?$(P^{NP})^+$$PH^+=PH$

Bisakah kita menebak apa kelas compexity sehingga C + adalah yang ideal direntang oleh C ?$C$$C^+$$C$

Jadi pertanyaan betapa mudahnya tugas komputasi mensimulasikan algoritma A untuk 3-SAT (ketika kita dapat memilih algoritma untuk membuatnya semudah mungkin) adalah kasus khusus yang menarik.

3) Apakah ada harapan untuk benar-benar membuktikan sesuatu tentang operasi ini?

Tentu saja, jika Anda membuktikan bahwa semua kelas kompleksitas masuk adalah P-space keras ini akan menunjukkan bahwa P = N P menyiratkan P = P S P A C E , yang (saya pikir) akan menjadi hasil yang sangat besar dan sangat tidak terduga . Tetapi jika Anda menunjukkan bahwa semua kelas kompleksitas dalam N P + sulit untuk dikatakan, katakanlah pada tingkat ketiga Hieararki polinomial (mis. Δ $NP^+$$P=NP$$P=PSPACE$$NP^+$ ) ini hanya akan menyiratkan hal-hal yang sudah kita ketahui, hal-hal yang mengikuti fakta bahwa P=NPmenyebabkan PH runtuh.$\Delta_3^{\bf P}$$P=NP$

Masalah: Misalkan A menjadi algoritma deterministik untuk 3-SAT. Apakah masalah sepenuhnya mensimulasikan algoritma A (pada setiap contoh masalah) P-Space sulit?

Saya tidak mengerti pernyataan masalah ini. Tapi saya pikir ada cara alami untuk memformalkan pertanyaan Anda yang lebih umum yang mungkin sedikit menjelaskannya. Mungkin saya benar-benar kehilangan maksud Anda, tetapi semoga Anda masih menemukan sesuatu yang menarik untuk dibaca di sini.

1) Apakah definisi itu masuk akal (dalam arti luas dari kata akal). Apakah itu dikenal atau sama dengan (atau mirip dengan) beberapa hal yang diketahui. (Formulasi saya bersifat informal dan khususnya ketika kita beralih dari masalah khusus seperti SAT ke kelas kompleksitas seperti NP kita harus khawatir tentang berbagai hal yang saya abaikan.)

Salah satu cara untuk memahami tugas dengan tepat adalah mensimulasikan algoritma $Y$ adalah sebagai berikut. Mari kita perbaiki model menjadi mesin Turing satu-pita untuk kesederhanaan; apa yang akan saya katakan dapat diterapkan pada setiap model komputasi yang khas.

Untuk setiap algoritme dan input x , kita dapat menentukan riwayat komputasinya H Y ( x , i , j ) : Diberikan bilangan bulat i dan j yang berkisar dari 0 hingga waktu berjalan Y , H Y$Y$$x$ $H_Y(x,i,j)$$i$$j$$0$$Y$ sama dengan isisel j dari pita mesin Turing Y pada input x pada langkah waktu i . (Dan jika kepala kaset sedang membaca$H_Y(x,i,j)$$j$$Y$$x$$i$$j$sel ke- $i$ langkah th, termasuk itu juga bersama dengan negara mesin.) Tentu saja, sejarah komputasi datang semua waktu dalam teori kompleksitas.

Sekarang, orang dapat berargumentasi bahwa algoritma apa pun yang dapat menentukan bahasa

$C_Y = \{(x,i,j,\sigma)~|~H_Y(x,i,j)=\sigma\}$

(atau mensimulasikan fungsi pada semua input) yang memecahkan tugaspersis algoritma simulasi Y , karena memiliki kemampuan untuk mencetak setiap sedikit bagian dari setiap perhitungan kemungkinan algoritma Y . Tentu saja, diberi oracle untuk C Y orang bisa melakukan simulasi langkah-demi-langkah Y .$H_Y$$Y$$Y$$C_Y$$Y$

2) Misalkan kita melengkapi diri kita dengan semua dugaan standar tentang kompleksitas komputasi. Bisakah kita mengatakan apa itu C + seharusnya untuk beberapa kelas kompleksitas yang akrab. (Misalnya C = NP, C = P-space, ..)? Bisakah kita menebak apa kelas kompleksitas C sehingga C + adalah ideal yang dibentang oleh C?

Ini masih merupakan pertanyaan yang menarik, di bawah proposal di atas. Untuk kelas waktu deterministik, tidak ada yang berubah. hanya P : kita bisa memutuskan C Y di polytime, untuk setiap algoritma polytime. Demikian E X P + = E X P . Juga P S P A C E + masih P S P A C E . Untuk kelas kompleksitas waktu nondeterministik, situasinya menjadi lebih menarik. Dalam hal itu, suatu algoritma Y dapat memiliki banyak sejarah komputasi, jadi$P^+$$P$$C_Y$$EXP^+ = EXP$$PSPACE^+$$PSPACE$$Y$$H_Y$ tidak lagi didefinisikan dengan baik. Namun kami masih ingin mencetak beberapa histori komputasi, jadi "simulasi persis" kami harus mengisolasi histori komputasi nondeterministik tertentu dan kemudian mencetak nilainya. Untuk algoritma Y , dapat dikatakan bahwa C Y$NP$$Y$$C_Y \in P^{NP}$ : kita dapat menggunakan oracle dengan pencarian biner untuk "pertama" menerima sejarah perhitungan (dalam urutan lex), kemudian setelah kami telah memperoleh itu, cetak bit yang relevan. Untuk algoritma N E X P Y , dapat dikatakan C $NP$$NEXP$$Y$ , untuk alasan yang sama.$C_Y \in EXP^{NP}$

Bisakah kita menempatkan di kelas yang lebih kecil? Saya tidak tahu Perhatikan kita tidak bisa hanya mendefinisikan ulang$NP^+$

{ ( x , i , j , σ ) | ada H Y sedemikian rupa sehingga H Y ( x , i , j ) = σ }$C_Y =$$(x,i,j,\sigma)~|~$$H_Y$$H_Y(x,i,j)=\sigma$

untuk mencoba menempatkan di N P , karena kita membutuhkan string sejarah yang sama untuk semua empat kali lipat yang melibatkan x , untuk "persis mensimulasikan algoritma $C_Y$$NP$$x$$Y$ ".

Pokoknya, masalah ini tidak dapat "mencetak saksi" untuk perhitungan tanpa pergi ke E X P N P memang muncul dalam beberapa situasi, seperti kompleksitas sirkuit. Jika N E X P memiliki sirkuit ukuran polinomial, maka apakah demikian halnya dengan C Y ∈ $NEXP$$EXP^{NP}$$NEXP$ untuk setiap nondeterministic 2 n k waktu Y ? Impagliazzo, Kabanets, dan Wigderson$C_Y \in P/poly$$2^{n^k}$$Y$menjawab pertanyaan ini dengan tegas pada tahun 2001. Bukti mereka sangat menarik, menggunakan alat dari derandomisasi dan diagonalisasi (mengapa derandomisasi diperlukan untuk hasil seperti itu?) dan ternyata menjadi teorema yang sangat berguna untuk membuktikan batas bawah sirkuit untuk Fungsi $NEXP$

Adakah harapan untuk benar-benar membuktikan sesuatu tentang operasi ini?

Mungkin ... itu tergantung pada apakah Anda senang dengan formalisasi pertanyaan Anda di atas. Untuk algoritma 3-SAT deterministik , saya pikir simulasi tepat atas masalah Y adalah P N P ( 1 ) -hard, di mana P N P ( 1 ) adalah waktu polinomial dengan satu kueri ke $Y$$Y$$P^{NP(1)}$$P^{NP(1)}$ . (Sintaks yang menjengkelkan dari StackExchange mengharuskan saya menulis (1) alih-alih alternatif. Sebelumnya saya mengatakan C Y harus P N P-keras , tapi saya tidak yakin detailnya: Anda mungkin melihat bagaimana menggeneralisasi di bawah ini.)$NP$$C_Y$$P^{NP}$

Kami memberikan polytime banyak-satu pengurangan dari setiap ke C Y . Diberikan L seperti itu , misalkan M menjadi mesin yang mengenali L yang melakukan permintaan N P tunggal . WLOG, permintaan itu adalah rumus SAT. Juga WLOG, kueri SAT dapat "ditunda" hingga langkah terakhir perhitungan, dalam arti berikut: ada algoritma waktu polinomial A ( x ) yang mencetak rumus F dan bit b , sehingga untuk semua x ,$L \in P^{NP(1)}$$C_Y$$L$$M$$L$$NP$$A(x)$$F$$b$$x$

menerima iff A ( x ) = ( F , b ) sedemikian rupa sehingga ( S A T ( F ) XOR b ) = 1.$M(x)$$A(x)=(F,b)$$SAT(F)$$b$

( dapat menolak jika F memuaskan, atau dapat menerima; bit b menangkap ini.)$M$$F$$b$

Untuk kesederhanaan, katakanlah ketika mengakhiri komputasinya, ia memindahkan head tape-nya ke sel 1, menulis "menerima" atau "menolak" di dalam sel itu, dan berputar selamanya. Kemudian, menanyakan apakah ( F , T , 1 , a c c e p t ) ∈ C Y untuk T yang cukup besar akan memberi tahu kami jika F diterima. (Secara umum, kita hanya perlu bahwa itu efisien untuk menghitung contoh y dari$Y$$(F,T,1,accept) \in C_Y$$T$$F$$y$ yang akan memberitahu kita.) Catatan ini sudah menunjukkan bahwa C Y adalah baik N P -Hard dan$C_Y$$C_Y$$NP$ -hard; yang terakhir adalah benar karena ( F , T , 1 c t ) ∈ C Y IFF F adalahtidaksatisfiable.$coNP$$(F,T,1,reject) \in C_Y$$F$

Pengurangan akhir dari ke C Y adalah: diberikan x , jalankan A ( x ) mendapatkan ( F , b ) . Jika b = 0 maka output ( F , T , 1 , a c c e p t ) , jika b = 1 output ( F , T , 1 , r e j e c $L$$C_Y$$x$$A(x)$$(F,b)$$b=0$$(F,T,1,accept)$$b=1$$(F,T,1,reject)$.

Untuk setiap kami memproduksi (dalam waktu polinomial) a y sehingga $x$$y$ menerima IFF y ∈ C Y .$M(x)$$y \in C_Y$

(Terima kasih kepada Joe karena menuntut agar aku lebih jelas tentang bagian ini.)

Tapi saya tidak melihat (misalnya) bagaimana cara mendapatkan kekerasan. Untuk mengurangi Σ 2 -SAT pada masalah, tampaknya Anda harus menulis instance 3-CNF x yang mensimulasikan algoritma deterministik Y Anda di dalamnya (di mana $\Sigma_2 P$$\Sigma_2$$x$$Y$$Y$ sedang menyelesaikan Tautologi pada berbagai subproblem). Tetapi karena tidak memiliki batas waktu tertentu, 3-CNF x itu bisa sangat besar, jadi Anda tidak perlu mendapatkan pengurangan waktu polinomial. Kecuali saya kehilangan sesuatu.$Y$$x$

Awalnya saya memposting jawaban yang salah, jadi semoga ini merupakan peningkatan.

Saya akan memulai dengan mempertimbangkan contoh 3SAT. Dalam komentar Anda tentang jawaban Ryan, Anda katakan

Saya menarik betapa sulitnya untuk mensimulasikan algoritma deterministik Y untuk 3-SAT. Dan pertanyaannya adalah jika tidak peduli apa Y ini P-space sulit.

Jawaban untuk ini adalah bahwa itu bukan PSPACE-hard untuk setidaknya beberapa Y, dengan asumsi bahwa NP PSPACE, tetapi bahwa ada algoritma lain yang itu adalah PSPACE-hard. Menampilkan yang terakhir itu sepele: Kami hanya membangun sebuah algoritma yang menafsirkan string bit yang mewakili rumus 3SAT sebagai masalah TQBF, yang kemudian diselesaikan sebelum memecahkan contoh 3SAT. Jelas tidak ada yang istimewa tentang TQBF dalam kasus ini, sehingga algoritma dapat dibuat sulit untuk disimulasikan. Jadi kita seharusnya hanya peduli pada batas bawah pada simulasi algoritma apa pun untuk masalah yang diberikan, bukan algoritma tertentu.$\neq$

Dengan mengingat hal itu, kami membuat algoritme berikut untuk menyelesaikan 3SAT:

Ambil register bit (awalnya semua diatur ke 0) untuk berisi solusi uji coba, bersama dengan register yang berisi instance 3SAT, register penghitung ukuran ⌈ log 2 ( c + 1 ) ⌉ awalnya diatur ke 1 dan dan dua flag bit (sebut ini bendera gagal dan bendera terima). Di sini c adalah jumlah klausa. Algoritma kemudian melanjutkan sebagai berikut:$n$$\lceil\log_2 (c + 1)\rceil$$c$

• Jika nilai penghitung klausa kurang dari atau sama dengan c , dan solusi percobaan tidak 111 ...... 1 , periksa apakah klausa$k$$c$$111......1$ puas. Jika tidak mengatur bit gagal. Tambahkan penghitung.$k$
• Jika nilai penghitung klausa kurang dari atau sama dengan c , dan solusi uji coba adalah 111 ...... 1 , periksa apakah klausul $k$$c$$111......1$$k$ puas. Jika tidak, atur bendera gagal. Tambahkan penghitung.
• Jika melebihi c , dan solusi uji coba tidak 111 ...... 1 , periksa apakah flag gagal diatur. Jika demikian maka tambahkan solusi uji coba, setel ulang penghitung k ke 1, dan hapus flag gagal. Jika bendera gagal tidak disetel, atur bendera terima, atur penghitung klausa k ke nol, atur solusi percobaan ke nol dan hentikan.$k$$c$$111......1$$k$$k$
• Jika melebihi c , dan solusi uji coba adalah 111 ...... 1 , periksa apakah flag gagal diatur. Jika bendera gagal tidak disetel, atur bendera terima. Atur penghitung klausa k ke nol, setel solusi uji coba ke nol dan hentikan.$k$$c$$111......1$$k$

Saat algoritme berhenti, keadaan tanda terima memberi tahu Anda apakah rumus 3SAT dapat dipenuhi atau tidak.

Sekarang, jika saya ingin menghitung keadaan algoritma pada waktu saya memiliki algoritma untuk menghitung ini dalam waktu polinomial dengan satu panggilan ke oracle NP sebagai berikut:$i$

Perhatikan bahwa untuk setiap , dengan asumsi bit terima belum ditetapkan, keadaan register dapat dihitung dalam waktu polinomial, karena nilai k dan register solusi uji t adalah fungsi sederhana dari i . Menentukan apakah flag gagal diset dapat dilakukan dalam waktu polinomial, cukup dengan memeriksa apakah keadaan saat ini dari daftar solusi percobaan memenuhi semua klausa kurang dari atau sama dengan nilai saat ini dari $i$$k$$t$$i$$k$ . Jika dan hanya jika ini tidak terjadi, bendera gagal diatur. Bendera terima diatur ke nol.

Demikian pula, jika bit terima telah ditetapkan, keadaan register dapat dihitung secara efisien, karena semuanya nol kecuali bit terima, yang ditetapkan.

Jadi satu-satunya kekerasan datang dalam menentukan apakah bit terima diatur. Ini setara dengan menentukan apakah instance 3SAT yang diberikan memiliki solusi kurang dari . Jika ya, maka bit yang diterima harus diatur, dan jika tidak, maka bit yang diterima harus nol. Jelas masalah ini dengan sendirinya NP-complete.$t$

Dengan demikian keadaan sistem pada langkah dapat ditentukan dalam waktu polinomial dengan satu kueri ke oracle NP.$i$

Pembaruan penting: Awalnya saya salah membaca perumusan Ryan tentang simulasi yang tepat sebagai masalah keputusan, sehingga klaim saya bahwa versi keputusan di NP tidak benar. Mengingat masalah memutuskan apakah bit pada langkah i pada input $j$$i$$x$ sebagaimana dirumuskan dalam jawaban Ryans, maka ada 3 kemungkinan:

1. Bit ini konstan dalam independen dari apakah memuaskan. Karena hanya ada dua keadaan yang mungkin untuk sistem saat ini (keduanya dapat dihitung dalam P) menentukan apakah ini masalahnya, dan jika demikian, apakah nilainya sama dengan $F$$\sigma$ dalam P.
2. Bit sama dengan jika F ∈ S A T , dan tidak setara jika tidak. Masalah ini jelas dalam NP, karena penugasan F yang memuaskan bertindak sebagai saksi.$\sigma$$F\in SAT$$F$
3. Bitnya sama dengan jika F ∈ U N S A T dalam hal ini masalahnya kemudian dalam coNP.$\sigma$$F\in UNSAT$

Jelas memutuskan mana salah satu dari tiga ini adalah kasus dapat dilakukan dalam waktu polinomial, hanya dengan membandingkan nilai yang sedikit memakan waktu jika dan jika F ∈ U N S A T . Dengan demikian masalah simulasi yang tepat adalah dalam NP ∪ coNP. Jadi, karena batas bawah Ryan dan pertandingan batas atas saya, dengan asumsi keduanya benar, saya pikir kami punya jawaban: C Y = N P ∪ c o N $F\in SAT$$F\in UNSAT$$\cup$$C_Y = NP\cup coNP$ .

Perhatikan bahwa tidak ada yang istimewa tentang 3SAT dalam kasus ini, dan hal yang sama dapat dilakukan untuk masalah apa pun di NP. Lebih lanjut, trik yang sama dapat digunakan untuk kelas kompleksitas non-deterministik, bukan hanya NP, yang tampaknya sulit untuk disimulasikan. Untuk kelas deterministik Anda cukup menjalankan algoritma terbaik dan berhenti pada langkah . Jadi dengan pemikiran ini, simulasi penuh setidaknya beberapa algoritma deterministik untuk suatu masalah hanya sekeras memecahkan masalah itu sendiri.$i$

Pikiran yang sangat menarik! Berikut komentar panjang yang terlalu panjang untuk dikirim:

Mengenai definisi dalam (1) seperti itu , yaitu:

Mulai dengan kelas kompleksitas yang dijelaskan oleh beberapa tugas komputasi. Mengingat algoritma A untuk melakukan setiap contoh tugas komputasi ini, mempertimbangkan kelas kompleksitas baru C A yang digambarkan oleh tugas komputasi completly simulasi A . Maka kita dapat (mudah-mudahan) mendefinisikan "ideal" dari kelas kompleksitas: C + = { C A : untuk semua algoritma A } .$C$$C_A$$A$$C^+ = \{C_A:$$A\}$

Saya percaya Anda akan dengan cepat mengalami masalah dengan keraguan untuk keanggotaan non-sepele di . Secara khusus, mengingat deskripsi dua TM M dan M ′ , diketahui bahwa memutuskan apakah mereka menerima bahasa yang sama (yaitu L ( M ) ? = L ( M ′$C^+$$M$$M^{\prime}$$L(M) \stackrel{?}{=} L(M^{\prime})$ tidak dapat diputuskan secara umum dengan pengurangan dari Masalah Pemutusan.

Selanjutnya, mengingat deskripsi dari Turing Machine , selalu ada simulasi sepele: Hanya membangun Turing Machine baru yang menyebut M sebagai sebuah sub rutin (menggunakan deskripsi), yang menerima jika M menerima dan menolak jika M menolak. Ini hanya biaya overhead linear. Secara khusus, jika M berjalan di t ( n ) langkah-langkah komputasi, maka M * berjalan di O ( t ( n ) ) (dimana "run," Maksudku "mensimulasikan M tepatnya").$M^*$$M$$M$$M$$M$$t(n)$$M^*$$O(t(n))$$M$

Ini menunjukkan kepada saya bahwa jika ada daya tarik serius yang dapat diperoleh di sini, cara yang tepat Anda tentang membuat definisi ideal dari kelas kompleksitas akan menjadi sangat penting. Secara khusus, jika Anda berniat untuk menunjukkan bahwa ideal, katakanlah, adalah P S P A C E -Hard, Anda harus mengesampingkan gagasan sepele, linear-waktu simulasi dari N P mesin di pertanyaan.$NP$$PSPACE$$NP$

Sehubungan dengan metode homotopy yang dijelaskan dalam pembicaraan / makalah dan GPS hasil kelengkapan, saya percaya "celah" yang Anda saksikan antara P P A D- kelengkapan dan P S P A C E- Kekerasan disebabkan oleh perbedaan antara menemukan NE mana pun (dalam arti END OF LINE) dan menemukan NE unik yang diberikan konfigurasi awal yang spesifik (dalam arti OTHER END OF LINE).$PSPACE$$PPAD$$PSPACE$