Pertanyaan yang diberi tag proof-search

Jika P = NP, bisakah kita mendapatkan bukti dugaan Goldbach dll?

Ini adalah pertanyaan naif, dari keahlian saya; permintaan maaf sebelumnya. Dugaan Goldbach dan banyak pertanyaan lain yang tidak terpecahkan dalam matematika dapat ditulis sebagai rumus pendek dalam predikat kalkulus. Misalnya, makalah Cook "Dapatkah Komputer Secara Rutin Menemukan Bukti...

Teorema jumlah langsung untuk Resolusi ruang klausa kompleksitas?

Resolusi adalah skema untuk membuktikan ketidakpuasan CNF. Bukti dalam resolusi adalah deduksi logis dari klausa kosong untuk klausa awal CNF. Khususnya setiap klausa awal dapat disimpulkan, dan dari dua klausa dan klausa A \ lor B dapat disimpulkan juga. Sangkalan adalah urutan pemotongan yang...