adalah

8

Saya pikir kedua kelas ini harus sama, tetapi saya tidak dapat menemukan literatur tentang hal ini dan memiliki latar belakang yang terbatas pada topik tersebut.

Ini adalah alasan saya, dan saya ingin tahu apakah (1) ini sudah diketahui atau (2) saya salah mengerti sesuatu atau (3) saya baru menemukan sesuatu yang berguna:

PCTC adalah kelas masalah yang dapat diselesaikan dengan menempatkan jumlah polinom data dalam mesin waktu.

BPPpath adalah kelas masalah yang dapat dipecahkan dengan memilih di mesin Turing probabilistik, yaitu mengabaikan kasus yang tidak Anda pedulikan.

PCTC⊆BPPpathkarena Anda dapat mensimulasikan kurva mirip waktu yang ditutup dengan pilihan pasca seperti ini: Pindai seluruh program di awal, baik status dan memori. Kemudian, setelah pemrosesan, lakukan lagi dan pilih dulu sehingga Anda hanya kembali jika status & memori sekarang persis sama dengan status awal & memori (kecuali untuk satu bit yang mengatakan apakah ini adalah iterasi pertama, untuk mencegah infinite loop).

BPPpath⊆PCTC karena Anda dapat mensimulasikan pemilihan pasca seperti ini: Jika pesan dari masa depan dimulai dengan 1, kirim pesan 0ke masa lalu. Kalau tidak, lanjutkan seperti biasa. Ketika Anda sampai pada langkah di mana Anda biasanya memposting, pilih 1 ke iff masa lalu. Anda ingin mengabaikan timeline ini, kalau tidak a0. Satu-satunya versi yang konsisten sekarang adalah versi di mana Anda berdua menerima dan mengirim 0 karena Anda puas dengan hasilnya.

complexity-theory complexity-classes quantum-computing Florian Dietz
sumber
2
Saya sama sekali tidak tahu tentang topik ini, tetapi, dalam tautan makalah ini mereka mengatakan bahwa kelas P_CTC sama dengan PSPACE dan BPP_PATH sama dengan POST_BPP yang terkandung dalam P dengan NP oracle. Jadi kedua kelas itu mungkin tidak sama
rotia
Itu menyenangkan untuk diketahui! Saya tidak akan mengatakan ini menunjukkan bahwa kedua kelas tidak sama, meskipun: Itu hanya berarti bahwa jika mereka sama, maka PSPACE = P ^ NP. Itu membuatnya lebih kecil kemungkinannya menjadi benar karena orang lain bisa saja menemukan hubungan ini sebelumnya jika itu benar, tetapi itu juga berarti bahwa JIKA pendekatan itu benar, maka itu akan memiliki konsekuensi yang bermanfaat.
Florian Dietz
Sketsa bukti Anda bahwa "P_CTC ada di BPP_PATH" adalah penyebab dalam pandangan saya. Satu masalah adalah tidak jelas bagaimana mesin postBPP Anda dengan benar mempertahankan status jumlah polinomial register CTC yang konsisten. P_CTC bukan hanya waktu polinomial dengan perjalanan waktu. Ada kriteria konsistensi sebab akibat yang sangat spesifik yang perlu ditegakkan. Kendala-kendala inilah yang memberi mesin kemampuan untuk menemukan titik-titik tetap parsial dengan mudah, yang bisa dibilang lebih umum daripada sekadar pemilihan pos. Saya mendorong Anda untuk hati-hati meninjau kembali definisi formal P_CTC.
mdxn

Jawaban:

0

Saya yakin saya telah menemukan jawabannya: Buktinya salah. BPP_PATH tidak ada di P_CTC karena P_CTC diharuskan untuk memberikan jawaban tunggal yang pasti, sedangkan BPP_PATH adalah algoritma probabilistik, sehingga reduksi kedua tidak berfungsi. Agar dapat bekerja, seseorang harus menggunakan informasi perjalanan waktu untuk menghitung jumlah keberhasilan algoritma probabilistik vs jumlah kegagalannya. Saya tidak tahu bagaimana melakukan ini, atau apakah itu bisa dilakukan (mungkin tidak).

Florian Dietz
sumber
... dan lima menit kemudian saya tidak lagi yakin. P_CTC = PSPACE, dan tidak bisakah PSPACE mensimulasikan BPP?
Florian Dietz
2
Anda membingungkan diri sendiri. Mesin deterministik pada dasarnya adalah mesin probabilistik dengan toleransi nol untuk kesalahan dan tidak ada akses ke keacakan. Jika mesin kandidat dapat menjawab pertanyaan yang sama tanpa kesalahan, maka tidak ada masalah. Tidak ada keharusan untuk salah sama seringnya. Apapun, PSPACE memungkinkan Anda mensimulasikan mesin BPP dengan mudah dengan bisa menguji setiap string acak dan secara manual menghitung probabilitas penerimaan. Karena P_CTC = PSPACE, itu beralasan bahwa ada beberapa mesin P_CTC setara yang dapat menjawab dengan cara yang sama diberikan mesin BPP tertentu.
mdxn