P dan Kompleksitas Deskriptif

10

Di Kebun Binatang Kompleksitas, ia mengatakan [ 1 ] itu, dalam kompleksitas deskriptif, P dapat didefinisikan oleh tiga jenis yang berbeda dari formula, FO(LFP) yang juga FO(nO(1)) , dan juga sebagai SO(HORN) .

Namun, ada beberapa pengecualian, misalnya, Evenness tidak bisa diungkapkan oleh FP (FP memiliki kekuatan ekspresif yang sama dengan LFP). Connectivity dan 2−colourability tidak dapat didefinisikan oleh logika orde pertama. Beberapa masalah bahkan tidak dapat di Aksioma dengan sejumlah variabel terbatas seperti Evenness ,Perfect Matching ,Hamiltonicity .

Immerman mengusulkan bahwa Fixed Point Logic + Counting (FPC) mungkin merupakan logika yang mungkin untuk menangkap P.

Namun, Cai Furer, Immerman menunjukkan bahwa ada sifat grafik polinomial-waktu yang tidak dapat diungkapkan dalam FPC [ 2 ]. Masalah penyelesaian persamaan linear pada bidang dua elemen tidak dapat didefinisikan dalam logika infinitary dengan penghitungan [ 3 ]. Anda bisa merujuk ke [ 4 ] untuk lebih jelasnya.

Jadi, struktur logika apa yang dapat menangkap P secara umum? Jawaban positifnya adalah bahwa kelas dari struktur berhingga yang terurut dapat didefinisikan dalam setidaknya logika titik-tetap jika, dan hanya jika, dapat ditentukan dalam P oleh Immerman [ 5 ] dan Vardi [ 6 ]. Bagaimana dengan kasus unordered? Bisakah Anda menunjukkan lebih banyak contoh berlawanan dari pernyataan di kebun binatang kompleksitas?

lo.logic polynomial-time descriptive-complexity Rupei Xu
sumber
2
Berikut ini adalah tutorial yang memberikan ikhtisar hasil pada pertanyaan khusus ini: cl.cam.ac.uk/ ~ ad260
Denis
@Denis Terima kasih, Denis! Tutorial ini mengandung lebih banyak struktur logika untuk P. Secara tradisional ketika kita berbicara tentang masalah adalah waktu polinomial yang dapat dipecahkan, kami pikir ini "mudah". Namun, struktur logika P terlihat sangat rumit, dan masih ada banyak kasus yang tidak diketahui dan masalah terbuka.
Rupei Xu
1
Ya, akan tampak bahwa serangkaian masalah "mudah" (yaitu P) tidak terstruktur dengan baik, dan sulit untuk dikarakterisasi dengan sesuatu seperti "masalah mudah adalah yang dapat diperoleh dari masalah dasar A, B, C, dikombinasikan dengan cara X, Y ". Selalu ada masalah yang lebih mudah yang berasal dari jenis lain, dan memerlukan algoritma polinomial cerdas dengan ide-ide baru di dalamnya.
Denis

Jawaban:

2

Martin Grohe membuat kemajuan besar pada pertanyaan ini baru-baru ini. Dia memberikan logika menangkap waktu polinomial pada kelas grafik yang dapat disematkan di permukaan yang tetap: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Sunting: kasus umum tampaknya tidak terselesaikan (tapi saya sama sekali tidak terselesaikan) ahli dalam hal ini).

Hermann Gruber
sumber
Iya. Ada banyak hasil meta-teorema algoritmik (seperti teorema Courcelle yang terkenal) dapat menangkap kasus-kasus yang mudah, tautan berikut adalah makalah survei yang baik. people . tidak ada struktur logika lengkap yang dapat menangkap P dalam grafik umum tanpa urutan sejauh ini.
Rupei Xu
Saya kira pekerjaan Grohe cukup istimewa karena dalam hal ini logika menghabiskan semua P pada kelas grafik yang sangat besar, yaitu tidak ada contoh tandingan. Jika saya melakukannya dengan benar, menjadi lengkap adalah bagian yang sulit. Hasil MSO yang Anda sebutkan tampaknya tidak memiliki fitur ini. Tapi saya keahlian saya dalam hal ini sangat terbatas, saya mungkin salah di sini.
Hermann Gruber