AI OpenAI dan Claude bilang teori komputer 25 tahun salah. Beneran?

OpenAI mengumumkan AI internalnya membuktikan bahwa sebuah dugaan penting di ilmu komputer, Exponential Time Hypothesis (ETH), ternyata salah. Dugaan ini dipegang lebih dari 25 tahun dan dipakai di ratusan makalah. Di hari penemuan yang sama, 16 Oktober 2026, model riset Claude milik Anthropic juga menemukan bantahan serupa, secara terpisah. Beneran? Buktinya sudah lolos pemeriksaan program komputer, tapi para ahli baru mulai memeriksanya. Dan kata Anthropic sendiri, hasil ini belum berpengaruh ke komputer sehari-hari.

Teorinya soal apa

Bayangkan teka-teki saklar. Ada sekian banyak saklar yang masing-masing bisa nyala atau mati, plus sederet aturan ("kalau saklar A nyala, B atau C harus mati"). Tugasnya: cari susunan saklar yang memenuhi semua aturan. Di ilmu komputer, soal ini disebut 3-SAT.

Cara paling polos adalah mencoba semua kemungkinan. Dengan 100 saklar saja, kemungkinannya lebih dari sejuta triliun triliun. Sejak 1999, Russell Impagliazzo dan Ramamohan Paturi menduga tidak ada jalan pintas yang benar-benar jauh lebih cepat dari itu: waktunya tetap naik berlipat-lipat setiap saklar bertambah. Dugaan inilah ETH. Banyak hasil lain dibangun di atasnya, jadi kalau ETH salah, sebagian bangunan itu ikut goyah.

Kata OpenAI: dugaan itu salah

Dalam pengumuman 26 Oktober 2026 (27 Oktober dini hari WIB), OpenAI menulis bahwa sistemnya "baru-baru ini membuktikan ETH salah", lalu buktinya diverifikasi dengan Lean, program yang memeriksa langkah-langkah bukti matematika secara otomatis.

Menurut OpenAI, AI-nya menemukan bantahan dalam bahasa biasa pada 16 Oktober, lalu menuliskannya dalam Lean sehari kemudian. Makalahnya (67 halaman) dibagikan terbuka di GitHub.

Claude juga menemukannya, di hari yang sama

Anthropic tidak mengumumkannya lewat akun media sosialnya. Tapi di repositori GitHub resminya, ada folder berisi makalah berjudul "A 2^o(n) Time Algorithm for 3-SAT" dengan penulis: Claude. README-nya menulis hasil ini membantah ETH dan ditemukan oleh model riset Claude internal.

Makalah itu menyebut algoritma intinya ditemukan pada 16 Oktober, tanpa masukan manusia, dan mencatat bahwa model OpenAI "secara independen dan bersamaan" mengklaim hasil serupa. Dua AI berbeda, dua jalan, tanggal penemuan sama.

Siapa yang memeriksa

OpenAI meminta pemeriksaan terbuka yang dipimpin Russell Impagliazzo dan Ramamohan Paturi (UC San Diego), dua orang yang merumuskan ETH, bersama Ryan Williams (MIT).

Williams menegaskan para pemeriksa tidak menandatangani perjanjian kerahasiaan dan tidak dibayar.

Kalau pembuktian AI dan teori ini terasa asing, kami pernah membahas AI lain yang ikut riset ilmiah: Claude merancang protein penangkal racun kalajengking.

Terus, komputer jadi lebih cepat?

Belum. README Anthropic menulis hasilnya "murni asimtotik", artinya hanya berlaku untuk soal yang sangat besar, dan tidak mengatakan apa pun soal menyelesaikan soal dalam praktik.

Di makalahnya, cara Anthropic diperkirakan baru terasa lebih unggul kalau saklarnya di atas kira-kira 10 juta. OpenAI juga menulis bahwa mengubah terobosan teori ini jadi peningkatan nyata masih butuh banyak riset.

Jadi, beneran?

• Yang sudah ada: dua AI berbeda mengklaim bantahan yang sama, dan bukti OpenAI lolos pemeriksaan Lean.
• Yang belum: belum ada ahli independen yang menyatakan buktinya benar. README Anthropic sendiri mencatat tidak ada mesin yang memeriksa bahwa pernyataan di Lean sama persis dengan isi makalahnya.
• Klaim lain: di halaman yang sama, OpenAI juga menyebut hasil di matematika (soal Kakeya) dan fisika (teori Yang–Mills). Keduanya masih diperiksa kelompok ahli masing-masing.

Pola "klaim besar dari pembuat AI, dicek dulu" juga kami pakai di cek fakta virus buatan AI, dan OpenAI sendiri baru merilis GPT-6.1 Terra sehari setelah pengumuman ini.

Foto sampul: Russell Impagliazzo (2016), BöhmMartin, CC BY-SA 4.0, Wikimedia Commons.

Lihat di Instagram

Versi singkatnya, lengkap dengan slide bukti, ada di Instagram @otaknologi: