Kegagalan Proses Editorial dan Kekeliruan Bukti P≠NP

Jurnal Frontiers of Computer Science menerbitkan makalah “SAT Requires Exhaustive Search” yang klaimnya lebih kuat dari P≠NP dan salah satu penulisnya adalah Wakil Pemimpin Editor jurnal tersebut.

Proses editorial jurnal tersebut gagal melibatkan pakar teori kompleksitas sehingga makalah dengan klaim besar tersebut terbit tanpa peninjauan yang memadai.

Eric Allender dan Ryan Williams menulis komentar yang menyoroti kekeliruan dalam bukti utama makalah dan meminta penarikan artikelnya.

Bukti utama makalah bertentangan dengan algoritma Ryan Williams (2005) yang menjalankan kasus khusus dalam waktu O(d^(0.8n)), membantah klaim lower bound.

Gregory Chaitin dikutip mendukung makalah dalam lampiran tetapi ia menyatakan tidak pernah membaca naskah tersebut.

Paragraf penutup komentar asli yang mengecam penerbitan sebagai aib jurnal dihapus dalam versi terbitan.

Penulis makalah merilis balasan resmi terhadap komentar Allender-Williams.

Makalah tersebut keliru dalam menyatakan batas bawah waktu tanpa asumsi batas ruang polinomial, padahal algoritma Williams menggunakan ruang kurang dari waktu yang diperlukan.