Apakah ada batasan alami logika VO yang menangkap P atau NP?

Kertas

• Lauri Hella dan José María Turull-Torres, Komputasi kueri dengan logika tingkat tinggi , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009

mengusulkan logika VO, variabel-order logic. Ini memungkinkan kuantifikasi atas pesanan atas variabel. VO cukup kuat dan dapat mengungkapkan beberapa pertanyaan yang tidak dapat dihitung. (Seperti yang ditunjukkan oleh Arthur Milchior di bawah, ini sebenarnya menangkap seluruh hirarki analitis .) Para penulis menunjukkan bahwa fragmen VO yang diperoleh dengan memungkinkan hanya kuantifikasi universal yang dibatasi atas variabel-variabel urutan persis mengekspresikan semua kueri kueri. VO memungkinkan variabel urutan untuk melampaui bilangan asli, jadi membatasi variabel urutan jelas merupakan kondisi alami untuk memaksakan.

Apakah ada fragmen VO (bagus) yang menangkap P atau NP?

Sebagai analogi, dalam logika orde pertama klasik yang memungkinkan kuantifikasi atas set objek memberikan logika yang lebih kuat yang disebut logika orde kedua atau SO. SO menangkap seluruh hierarki polinomial ; ini biasanya ditulis sebagai PH = SO. Ada bentuk terbatas dari SO menangkap kelas kompleksitas penting: NP = SO, P = SO-Horn, dan NL = SO-Krom. Ini diperoleh dengan menerapkan batasan pada sintaksis rumus yang diizinkan.$\exists$

Jadi ada cara mudah untuk membatasi SO untuk mendapatkan kelas yang menarik. Saya ingin tahu apakah ada pembatasan langsung yang serupa dari VO yang kira-kira tingkat ekspresivitas yang tepat untuk P atau NP. Jika pembatasan semacam itu tidak diketahui, saya akan tertarik pada saran untuk calon yang mungkin, atau dalam beberapa argumen mengapa pembatasan seperti itu tidak mungkin ada.

Saya telah memeriksa (beberapa) makalah yang mengutip ini, dan memeriksa frasa yang jelas di Google dan Cendekia, tetapi ternyata tidak ada yang relevan. Sebagian besar makalah yang berurusan dengan logika lebih kuat daripada orde pertama tampaknya tidak berurusan dengan pembatasan untuk menurunkan daya ke ranah komputasi "masuk akal", tetapi tampaknya puas tinggal di alam semesta kelas aritmatika dan analitik. Saya akan senang dengan pointer atau frase yang tidak jelas untuk dicari; ini mungkin diketahui oleh seseorang yang bekerja di logika tingkat tinggi.

Catatan: Ini tidak benar-benar menjawab pertanyaan, ini hanya beberapa komentar yang diposting sebagai jawaban. :)

$\exists$$PH$$P$$NP$

Apakah keberadaan satu quantifier tak terbatas cukup untuk menangkap set ce?

Masalahnya adalah Anda mungkin ingin bahasa menjadi tanpa simbol tambahan seperti kesetaraan, penambahan, perkalian (kanan?), Jika kita memilikinya maka dengan teorema MRDP, rumus Diophantine (kuantum eksistensial urutan pertama di depan kesetaraan dua polinomial) akan menangkap set ce. Jika kita tidak mengizinkan simbol-simbol ini dalam bahasa, masalahnya lebih rumit, kita dapat menggunakan quantifiers tingkat tinggi untuk mendefinisikannya, tetapi itu akan meningkatkan kompleksitas quantifier. Jadi jika saya ingin memberikan jawaban singkat untuk pertanyaan Anda tentang penjumlahan tunggal, saya tidak tahu.

$AC^0$$AC^0$$c$$e$$x$

Beberapa komentar tambahan:

$AC^0$

Sebagai informasi, VO sebenarnya lebih kuat dari yang Anda nyatakan; ini berisi seluruh hirarki analitik (karenanya, juga seluruh hierarki aritmatika). Hasilnya tidak dipublikasikan, tidak dikirim ke tempat mana pun, tetapi Anda dapat menemukannya di halaman saya, www.milchior.fr/ho.pdf bagian 7 halaman 47.

$\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$$\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$$i$$X$$^i$$X$

$\phi(i)$$i$$k$$i>k$$\phi(i)$$k$$\phi(i)$$\forall i \phi(i)$$\forall i < k \phi(i)$

Selain itu, Anda tentu dapat menahan VO dengan menahan urutan maksimal yang diterima; tetapi kemudian Anda memperoleh bahasa "urutan lebih tinggi" (HO), dan ini mungkin bukan yang Anda inginkan.

Untuk menjawab komentar Anda, saya kira saya harus membuat jawaban lain, hanya berbicara pada Krom dan Horn (Mungkin saya harus mengajukan pertanyaan tentang itu ke CSTheory)

Saya sarankan Anda membaca bagian 5.3 halaman 34 dari makalah saya tentang masalah yang saya temui di Horn dan Krom dalam logika Orde Tinggi. Anda akan menemui masalah yang sama dalam Urutan Variabel (yang jelas merupakan superset dari Orde Tinggi).

Saya tidak tahu apakah Anda memperhatikannya, tetapi SO (krom) sama dengan P ketika urutan pertama bersifat universal; memang Anda bisa mengekspresikan masalah NP-complete jika Anda menambahkan variabel first order existantial. (Saya tidak ingat contoh yang saya miliki sebelumnya, saya dapat mencoba mencarinya jika Anda menginginkannya)

Saya tidak tahu akan jadi apa resctriction sintaksis ini untuk logika orde tinggi atau variabel ... maksud saya adalah Anda juga harus memikirkan cara yang baik untuk menahan quantifiers, karena menahan bagian bebas quantifier saja tidak berguna ( setidaknya untuk formula Krom)