Apa definisi yang setara dari mP / poli dalam hal mesin Turing?

13

P / poly adalah kelas masalah keputusan yang dipecahkan oleh keluarga sirkuit Boolean ukuran polinomial. Alternatifnya dapat didefinisikan sebagai mesin Turing polinomial-waktu yang menerima string saran yang ukuran polinomial dalam n dan yang hanya didasarkan pada ukuran n.

mP / poli adalah kelas masalah keputusan yang dipecahkan oleh keluarga sirkuit Boolean monoton ukuran polinomial, tetapi apakah ada definisi alternatif alami mP / poli dalam hal mesin Turing polinomial waktu?

cc.complexity-theory complexity-classes circuit-complexity polynomial-time monotone Jesse Stern
sumber
3
AFAIK, kami tidak memiliki gagasan tentang mesin Turing yang sesuai dengan sirkuit monoton. Jadi jawabannya tidak.
Kaveh
Saya pikir itu mungkin terjadi. Adakah diskusi penting, baik online atau di surat kabar, tentang masalah kelas mengekspresikan dipecahkan oleh keluarga sirkuit ukuran terbatas yang monoton atau memiliki sejumlah negasi terikat, dalam hal waktu yang dibatasi mesin Turing? Apakah hambatan khusus mereka untuk mendefinisikan kelas seperti itu, atau membuat orang tidak terganggu?
Jesse Stern

Jawaban:

15

mPmP/halHaily

Jan Johannsen
sumber
7

Sebenarnya ada gagasan mesin Turing positif deterministik yang cocok dengan mP / Poly. Itu dapat ditemukan di artikel Positive Version of Polynomial Time oleh Lauteman, Schwentick dan Stewart

Thomas S
sumber