Redundansi dan Struktur masalah komputasi

11

Dipercaya secara luas bahwa beberapa masalah komputasi seperti grafik isomorfisme tidak dapat NP-lengkap karena tidak memiliki struktur atau redundansi yang cukup untuk menjadi komputasi yang sulit (NP-hard). Saya tertarik pada gagasan formal yang berbeda untuk struktur masalah komputasi dan langkah-langkah redundansi.

Apa hasil utama yang diketahui tentang gagasan formal untuk masalah komputasi? Sebuah survei terbaru tentang gagasan seperti itu akan sangat bagus.

EDIT: Diposting di MathOverflow

cc.complexity-theory graph-isomorphism Mohammad Al-Turkistany
sumber

Jawaban:

4

coAMNPNP

NP

(Di sisi lain, isomorfisma kelompok nampaknya bahkan lebih terstruktur daripada GI, namun tidak ada pengurangan jumlah-ke-keputusan yang diketahui untuk iso kelompok. Mungkin ini mengatakan bahwa GI berada dalam tingkat struktur yang "tepat" - terlalu terstruktur untuk menjadi NP-lengkap, tetapi cukup tidak terstruktur untuk memungkinkan pengurangan penghitungan-ke-keputusan.)

Joshua Grochow
sumber
Jadi, GI dalam beberapa hal tidak "acak" cukup untuk menangkap kelengkapan NP. Apakah ada gagasan formal yang menangkap kurangnya keacakan masalah GI?
Mohammad Al-Turkistany
1
Ya, salah satu anggapan seperti itu adalah bahwa GI tidak lengkap NP! :-) (Kecuali jika hierarki polinomial runtuh.)
Scott Aaronson
Jacobo Toran menyatakan "Ada kepercayaan umum bahwa GI tidak mengandung cukup struktur atau redundansi yang menyulitkan NP", TENTANG KEKERASAN ISOMORFISME GRAF, Jurnal SIAM tentang Komputer, 33 (5), 1093-1108. Masalahnya adalah kita tidak tahu bagaimana membuktikan non-kekerasan NP dari masalah NP alami.
Mohammad Al-Turkistany
Saya pikir mungkin pernyataan Toran dan milik saya adalah dua sisi dari mata uang yang sama: milik saya mengatakan bahwa contoh masalah individual terlalu terstruktur, dan salah satu akibatnya adalah bahwa bahasa GI secara keseluruhan tidak cukup berlebihan (pernyataan Toran). Kupikir. Tanpa benar-benar bertanya kepada Jacobo, sulit untuk mengatakannya.
Joshua Grochow