Pertanyaan yang diberi tag decidability

Masalah: Pertimbangkan sejumlah kondisi kontrol terbatas (termasuk status "awal" dan "buruk"), sejumlah variabel integer, dan untuk masing-masing pasangan negara terurut hubungan transisi yang dinyatakan dalam aritmatika Presburger. Putuskan apakah ada invarian induktif (= stabil oleh post-state...

Jawaban yang Diterima Jawaban Scott Aaronson telah "diterima" (terutama karena itu satu - satunya jawaban!) Ringkasan jawaban satu kalimat   Generalisasi yang wajar dan wajar dari pertanyaan P versus NP tidak jelas lebih mudah diselesaikan daripada P versus NP itu sendiri. Satu halangan terhadap...