3SUM ve APSP için ilk polinomiyel hızlanmalar, uzun süredir geçerli karmaşıklık varsayımlarını çürütüyor

Ders kitabı bariyerleri ikisi birden yıkılıyor

Yeni bir arXiv önbasımı, kuramsal bilgisayar biliminin en yoğun çalışılan problemlerinden ikisi olan 3SUM ve All-Pairs Shortest Paths (APSP) için ders kitabı algoritmalarına karşı ilk polinomiyel iyileştirmeleri iddia ediyor. Josh Alman tarafından 5 Ekim 2026'da gönderilen ve Hacker News ana sayfasında öne çıkan makale, polinomiyel boyutlu n tam sayı üzerinde deterministik bir 3SUM algoritmasının O(n^1.9992) sürede çalıştığını ve polinomiyel sınırlı tam sayı ağırlıklı yönlü n-tepe graflar üzerinde APSP algoritmasının O(n^2.9995) sürede çalıştığını bildiriyor.

Bağlam için: Standart 3SUM yaklaşımı — girdiyi sıralayıp iki işaretçiyle taramak — kuadratik zaman alır ve klasik Floyd–Warshall APSP algoritması kübik zaman alır. Her iki üstel de onlarca yıldır sabit bir iyileştirmeye direnç gösterdi; öyle ki ince taneli karmaşıklık kuramı bu direnci 3SUM hipotezi ve APSP hipotezi olarak kalıcılaştırdı: bu üstellerden sabit bir sabit kırılamayacağı varsayımları. Özete göre yeni sonuçlar ikisini de çürütüyor.

Her şeyin ardında tek bir algoritma

Makale her problemi ayrı ayrı eleştırmak yerine, her şeyi ince matris çarpımları için tek bir yeni yordamdan türetiyor. X bir N×D tam sayı matrisi ve Y bir D×N tam sayı matrisi olsun; burada D en fazla N^(1/18). En fazla N^2/√D konumdan oluşan herhangi bir W kümesi verildiğinde, yordam XY çarpımının girdilerini bu konumlarda O(N^2/D^0.063) işlemle hesaplıyor — bu da, özetin belirttiği üzere, tam çarpımı yazmaktan ya da gereken iç çarpımları tek tek hesaplamaktan polinomiyel ölçüde daha az.

Yapı, kendisi Schönhage'ye ait on çarpımlı bir özdeşlikten inşa edilen Coppersmith'in dikdörtgen matris çarpımı algoritmasının bir varyantını, yalnızca W'deki girdiler için gereken işlemleri gerçekleştirecek biçimde değiştiriyor ve az sayıda işlemin yeterli olduğunu kanıtlıyor.

Bir graf algoritması olarak okunduğunda, yordam All-Edges Sparse Triangle problemini — her kenar için, bir üçgende bulunup bulunmadığına karar vermeyi — seyrek ve dengesiz üç parçalı graflarda gerçekten alt-kuadratik zamanda çözüyor; bu, iki tarafın n tepe içerdiği ama üçüncünün yalnızca 0.12'den küçük bir ε için n^ε tepe içerdiği graf anlamına geliyor. Bilinen indirgemeler Exact Triangle'ı ve onun üzerinden 3SUM ile APSP'yi bu probleme indirgiyor. Makale ayrıca, önceden bilinmeyen XY girdileri için sorguları yanıtlayan bir veri yapısı sürümünü de tanımlıyor.

Çürütülen varsayımların zincirleme etkisi

3SUM ve APSP hipotezleri izole varsayımlar değil; ince taneli karmaşıklık boyunca koşullu alt sınırların temelini oluşturuyorlar. Makale, bilinen indirgemeleri kullanarak 3SUM ve APSP hipotezlerinin gerçek değerli sürümlerini, Exact Triangle hipotezini, Zero-Weight k-Clique hipotezlerini ve van den Brand, Nanongkai ve Saranurak'ın üç dikdörtgen ipuclu Online Matrix–Vector varsayımını da çürütüyor. Ayrıca çeşitli diğer problemler için de polinomiyel hızlanmalar bildiriyor.

Neden önemli

Anlık pratik kazanç muhtemelen sınırlı: 1.9992'lik bir üstel, 2'ye kıyasla yalnızca çok büyük girdi boyutlarında anlam kazanıyor ve bu, iddiaların kesinleşmesinden önce kanıtların yakından incelenmesi gereken, hakem değerlendirmesinden geçmemiş bir önbasım. Ancak kuramsal açıdan sonuç bir dönüm noktası. Alanın en eski ve en etkili iki varsayımını olumsuz yönde çözüyor ve onları kırmak için temelden yeni bir teknikten ziyade dikdörtgen matris çarpımının mevcut araçlarının yeterli olduğunu gösteriyor. Önemli miktarda koşullu zorluk sonucu artık çürütülmüş olan bu varsayımlara dayandığından, ince taneli karmaşıklık haritasının bazı bölümlerinin yeniden çizilmesi gerekecek.