Apakah ada masalah komputasi yang berada dalam waktu kuasi polinomial tetapi (mungkin) tidak dalam

Waktu quasi-polinomial, atau QP, adalah kelas kompleksitas pada mesin Turing deterministik. Berikut adalah definisi yang tepat: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

Sedangkan βP adalah kelas kompleksitas nondeterminisme terbatas. Berikut adalah definisi yang tepat: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Sangat mudah untuk melihat bahwa setiap mesin βP dapat disimulasikan oleh mesin QP, yaitu, βP QP. $\subseteq$

Tapi apakah kita punya contoh, masalah yang ada di QP tetapi tidak di βP, bahkan jika kita tidak punya bukti yang tepat bahwa masalahnya bukan di βP?

cc.complexity-theory complexity-classes Arthur Kexu-Wang
sumber

Biarkan f menjadi fungsi number_of_states_, dan pertimbangkan masalahnya

$\hspace{2.36 in}$ "Apakah M paling banyak berhenti (f (M))

langkah "?.

^{\log (f (M))}

$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$

Jawaban:

Sementara saya tidak tahu spesifik (menduga) misalnya di , masih ada bukti lebih meyakinkan bahwa adalah tepat bagian dari . Yaitu, kelas-kelas ini berperilaku sangat berbeda dalam hubungannya dengan : $QP-\beta P$ $\beta P$ $QP$ $NP$

Hal ini jelas dari definisi yang . $\bullet$ $\beta P\subseteq NP$

Di sisi lain, tidak diketahui, dan itu akan sangat sulit untuk membuktikan, karena mengandung arti . (Bahkan, itu adalah pernyataan yang bahkan lebih kuat dari ) $\bullet$ $QP\subseteq NP$ $P\neq NP$ $P\neq NP$

Seperti perilaku yang sangat berbeda dibandingkan dengan tampaknya memberikan alasan yang cukup kuat untuk percaya bahwa . $NP$ $\beta P\neq QP$

Andras Farago
sumber

Juga, tampaknya tidak mungkin untuk

ditutup di bawah komplemen.

β P

$\beta P$

Emil Jeřábek

Karena, seperti yang Anda sebutkan

menyiratkan

. Sebagai tindak lanjut, apa yang akan hasil dari

atau

menyiratkan dalam hirarki kompleksitas dan akan itu memiliki dampak pada

masalah?

Q P \subseteq N P

$QP\subseteq NP$

P \neq N P

$P\neq NP$

N P \subseteq Q P

$NP \subseteq QP$

N P \subset Q P

$NP \subset QP$

P v s N P

$P vs NP$

TheoryQuest1

Iya. Kami punya masalah seperti itu. Ini adalah masalah Graph Isomorphism. Babai membuktikan bahwa GI ada di QP . Pemahaman saya adalah bahwa bukti Babai tidak menghasilkan batas atas nondeterminisme terbatas ( ) pada kompleksitas GI. $\beta P$

Kami memiliki bukti bahwa GI dalam $\beta P$ . Selain itu, kami tidak memiliki bukti bahwa GI tidak dapat diselesaikan dengan menggunakan nondeterminisme poli-logaritmik.

Lihat posting terkait ini .

Posting Teori CS ini oleh @Salamon menunjukkan bahwa kita bahkan tidak tahu apakah GI dapat diputuskan dengan nondeterminisme dibatasi-akar kuadrat apalagi nondeterminisme poli-logaritmik.

Mohammad Al-Turkistany
sumber

Namun, saya pikir banyak orang menduga bahwa GI ada di P.

Thomas

@ Thomas Babai dalam makalahnya mengindikasikan bahwa dia menentang dugaan ini.

Mohammad Al-Turkistany

Apakah Anda yakin algoritma Babai tidak dalam

β P

$\beta P$

Joshua Grochow

@ MohammadAl-Turkistany Ironisnya, pertanyaan pada MO yang Anda kutip (baik dalam jawaban Anda dan komentar Anda) adalah oleh OP sendiri dari 10 bulan lalu, dan tidak memiliki jawaban (hingga hari ini). Saya tidak yakin seberapa banyak ini memberi kepercayaan pada argumen Anda - itu hanya menyiratkan bahwa "Kami tidak memiliki bukti bahwa GI dalam

dirujuk pada MathOverflow " di terbaik.

β P

$\beta P$

Clement C.

@ JoshuaGrochow Ya, komentar lebih spesifik (menunjukkan bagian spesifik tentang derajat). Tetapi jawabannya hanya merujuk pertanyaan pada MO sebagai apa yang saya ambil sebagai petunjuk kuat untuk klaim bahwa tidak ada bukti - yang terdengar melingkar bagi saya.

Clement C.