Masalah dengan solusi yang efisien kecuali untuk sebagian kecil input

Masalah penghentian untuk mesin Turing mungkin adalah set kanonik yang tidak dapat ditentukan. Namun demikian, kami membuktikan bahwa ada algoritma yang memutuskan hampir semua instance dari itu. Masalah penghentian karena itu di antara koleksi yang berkembang dari mereka yang menunjukkan "lubang hitam" fenomena teori kompleksitas, dimana kesulitan dari masalah yang tidak dapat ditentukan atau tidak dapat dipastikan terbatas pada wilayah yang sangat kecil, sebuah lubang hitam, di luar di mana masalahnya adalah mudah.

[Joel David Hamkins dan Alexei Miasnikov, " Masalah yang terputus-putus ditentukan pada seperangkat satu probabilitas asimptotik ", 2005]

Adakah yang bisa memberikan referensi ke "lubang hitam" lainnya dalam teori kompleksitas, atau tempat lain di mana konsep ini atau yang terkait dibahas?

cc.complexity-theory reference-request computability undecidability Jim Graber
sumber

Joel secara teratur mengunjungi MathOverflow, Anda dapat mengajukan pertanyaan di sini untuk mendapatkan jawaban darinya. IIRC ada pertanyaan tentang hasilnya di sana.

Kaveh

Lihat juga HeurP .

Kaveh

Mungkin contoh lain adalah Graph Isomorphism (yang merupakan masalah NP-intermediate). Pada "contoh nyata" sangat mudah (sepele untuk contoh acak?) Dan untuk banyak kelas grafik ada algoritma waktu polinomial. "Lubang hitam" kelihatannya sangat ketat sehingga tidak mudah untuk membuat instance yang sulit dan nakal, salah satu alat yang paling efisien untuk menyelesaikannya , sering digunakan untuk menghasilkan instance (keras). Tapi mungkin, "lubang hitam" akan lenyap dan akan meninggalkan GI yang malang di P :-D

Marzio De Biasi

@ Marszio, contoh dunia non-nyata biasanya tidak sepersekian kecil dari semua contoh dan berbeda dari apa yang mereka maksudkan di koran.

Kaveh

A

$A$

A^{'} = (A_{y}^{'}, A_{n}^{'})

$A' = (A'_y,A'_n)$

A_{y}^{'}

$A'_y$

A

$A$

A_{n}^{'}

$A'_n$

\bar{A}

$\bar{A}$

Masalah dengan solusi yang efisien kecuali untuk sebagian kecil input

Jawaban: