Postselection dalam teori kompleksitas geometris

Konteks: Seperti yang saya pahami, dalam teori kompleksitas geometris, keberadaan penghalang berfungsi sebagai sertifikat bukti, sehingga dapat dikatakan, untuk tidak adanya sirkuit komputasi yang efisien untuk fungsi keras eksplisit dalam masalah batas bawah yang sedang dipertimbangkan. Sekarang ada beberapa asumsi lain untuk penghalang bahwa mereka harus pendek, mudah diverifikasi dan mudah dibangun.

Pertanyaan: Pertanyaan saya adalah yang mengatakan bahwa saya memiliki masalah yang saya duga dapat diselesaikan dalam waktu polinomial. Lalu bagaimana saya bisa menunjukkan bahwa tidak ada halangan untuk masalah ini, yaitu jika tidak ada halangan maka masalahnya dapat dihitung secara efisien dan memang dalam waktu polinomial.

Pendekatan: Saya pikir, dan saya mungkin salah dalam pernyataan ini, bahwa menunjukkan tidak ada penghalang bisa setara dengan pengurangan standar masalah NP untuk masalah lain yang kompleksitasnya belum diketahui, dalam bukti bahwa mereka sendiri di NP. Jadi dalam hal ini seseorang dapat, jika mungkin, menunjukkan bahwa ada penghalang ketika seseorang mencoba untuk mengurangi masalah NP menjadi masalah yang sedang dipertimbangkan, dengan cara itu, pengurangan itu tidak bisa dilakukan. Juga peran apa yang dimainkan pasca pemilihan dalam semua ini? Apakah mungkin untuk hanya memilih setelah tidak ada penghalang? Terima kasih dan maafkan kurangnya pernyataan yang tepat dalam pendekatan dan pertanyaan saya.

Sebagai contoh lain, pertimbangkan masalah X yang kita tahu ada di P. Sekarang katakanlah kita tidak tahu tentang masalah yang dapat dipecahkan dalam waktu polinomial, maka apakah mungkin, bahwa seseorang dapat membuat pernyataan berikut:

Karena tidak ada penghalang dalam perhitungan X kita dapat mengatakan bahwa itu ada di kelas P

Dari sana, masalahnya adalah penemuan (penghitungan) yang mudah dari penghalang-penghalang itu, bahkan jika ada, akan menunjukkan bahwa X tidak dalam waktu polinomial. Namun sebaliknya, menemukan bahwa tidak ada penghalang adalah tugas yang sulit.

$P$

Untuk keperluan jawaban ini, kita dapat mempartisi program GCT Mulmuley-Sohoni menjadi dua langkah:

1. $perm$$det$$V_{perm}$$V_{det}$$V_{perm} \subseteq V_{det}$$perm$$p$$det$

2. $V_{perm} \not\subseteq V_{det}$

Perhatikan bahwa implikasi dalam (2) hanya berjalan satu arah (keberadaan obstruksi tidak menyiratkan dimasukkannya varietas), sehingga ada kemungkinan bahwa bukan proyeksi dari dan belum ada representasi-penghalang teoretis yang ada. Jadi dalam kasus ini, hanya membuktikan bahwa tidak ada penghalang tidak cukup untuk menunjukkan bahwa itu mudah. Di sisi lain, dalam (1) dimasukkannya varietas aljabar diperlukan dan cukup untuk dimasukkannya kelas kompleksitas.$perm$$p$$det$$perm$

[Dalam contoh di atas tentu saja banyak detail yang dihilangkan - ketergantungan pada ukuran input, bagaimana berbicara tentang kelas kompleksitas alih-alih , fakta bahwa dimasukkannya varietas setara dengan dapat diperkirakan oleh proyeksi , ... Tapi esensinya masih benar.]$P$$det$$perm$$p$$det$

Saya suka berpikir seperti ini juga, dan saya menautkannya dengan dugaan . Disebutkan di sana atau di sana (saya kesulitan menemukan halaman tentang dugaan ini karena saya hanya dapat merujuknya dengan simbol matematika yang tidak disukai Google).$P=NP\cap co-NP$

Masalah ada di NP ketika Anda bisa memberikan sertifikat untuk jawaban "Benar" (contoh: siklus hamiltonian untuk masalah TSP atau penugasan yang valid untuk masalah SAT). Ada dalam NP bersama ketika Anda dapat memberikan sertifikat untuk jawaban "Salah" (contoh: "bukti" bahwa rumus SAT tidak memuaskan, potongan buruk dalam grafik yang mencegah keberadaan siklus hamiltonian, dll. ..)

Sebenarnya, itu mungkin "penghalang" yang mungkin Anda rujuk juga. Dan dugaan ini adalah tentang mengatakan: masalah yang ada di NP adalah polinomial ketika saya tahu apa penghalang itu.

Sekarang, "penghalang" dapat mengambil berbagai bentuk. Untuk masalah pencocokan (yang polinomial) dapat berupa partisi dari grafik (lihat karakterisasi Tutte tentang grafik yang cocok dengan sempurna ), atau dapat berupa sertifikat yang diberikan oleh Lemma Farkas untuk pemrograman linier (dan masalah grafik yang dapat dikurangi untuk itu). Ini sebenarnya bisa menjadi banyak hal, jadi saya biasanya "menggunakan" dugaan ini dalam satu arah: Ketika saya tidak menemukan penghalang, saya tidak menyimpulkan bahwa masalah saya adalah NP-Hard. Beberapa penghalang benar-benar sulit ditemukan ... Tetapi ketika saya memiliki algoritma polinomial yang rumit untuk suatu masalah, saya kadang-kadang yakin bahwa "harus ada serangkaian penghalang yang dapat dimengerti, yang akan lebih mudah untuk memahami bahwa algoritma yang rumit".

Baiklah ... Dua sen saya :-)

Nathann