TOPLAMI TUTAN SAYILARI SEÇMEK, NEREDEYSE ONLARI OKUMAK KADAR HIZLI

İşte herkesin ifade edebileceği bir bulmaca. Bir tam sayı listeniz var — diyelim 3, 9, 14, 20 — ve bir hedef, diyelim 23. Bazılarını, toplamları hedefe tam olarak eşit olacak şekilde seçebilir misiniz? (Burada evet: 3 + 20 ya da 9 + 14.) Bu, bilgisayar biliminin en temel problemlerinden biri olan Subset Sum. Makale onu, tam olarak çözülmesinin zor olduğuyla bilinen bir problem ailesi olan temel bir NP-tam problem olarak tanımlıyor.

Ama bir açık kapı var. Sayılar çok büyük değilse, akıllı algoritmalar sayıların büyüklüğüne bağlı bir sürede çalışır. Bellman’ın 1957 tarihli klasik yöntemi, sayıların adedi n ile hedef t’nin çarpımıyla orantılı süre alır. O zamandan beri algoritmalar iyileşmeye devam etti:

• Pisinger (1999): n × N ile orantılı; burada N en büyük sayı;
• Bringmann (2017): kabaca n + t;
• birkaç ekip (2021–2024): kabaca n + N^(5/3), sonra n + N^(3/2).

Kutsal kâse, kabaca n + N süreydi — girdiyi okumaktan pek fazlası değil. Alandaki araştırmacılar buna bu çalışma hattının “en can alıcı açık problemi” demişti.

Hedefe kıl payı

Çin’deki Zhejiang Üniversitesi’nden Lin Chen, Yuchen Mao ve Guochuan Zhang, n + N^(1+ε) sürede çalışan bir algoritma veriyor; burada ε önceden sabitlenmiş herhangi bir küçük pozitif sayı olabilir — 0,1, 0,01, 0,001. Algoritma deterministik, negatif sayıları ve tekrarlanan değerleri kabul ediyor ve matematiksel bir ispatla geliyor. Yazarlar bu süreye neredeyse optimal diyor.

Sonuç vektörlere de genişliyor: öğeleri birkaç toplam aynı anda hedeflerini tutturacak şekilde seçmek, d koordinat için N^(d+ε) sürede. Bu da birkaç grubun tam sayılı programlama — değişkenleri sınırlı denklem sistemlerinin tam sayı çözümlerini bulmak — hakkında sorduğu bir sorunun bir kısmını yanıtlıyor. İki sonuç açıkça çıkarılıyor: bir sayı kümesini iki eşit yarıya bölmek ve işleri iki özdeş makine arasında olabildiğince eşit paylaştırmak.

Sayıları daha yüksek bir boyuta kaldırmak

Temel fikir geometrik. Sayılar yoğun olduğunda ve hedef olası toplamların aralığının epey içinde kaldığında problemin kolay olduğu zaten biliniyordu. Yazarların gözlemi şu: seyrek bir sayı kümesi, daha yüksek bir boyutta bakıldığında yoğun görünebilir.

Örnekleri {11, 12, 22, 24} kümesi. 11 ve 22’yi birinci eksen boyunca bir ve iki adım, 12 ve 24’ü ikinci eksen boyunca bir ve iki adım olarak yazın. Olası toplamlar o zaman küçük bir 4’e 4 karenin her noktasını dolduruyor. Ama bu kareyi bir doğruya geri bastırın — 11x + 12y hesaplayarak — toplamlar 0 ile 69 arasına dağılmış, aralarında boşluklar olan yedi ayrı küme oluşturuyor. Boşluklar izdüşümün bir yanılsaması; iki boyutta yapı basit.

Algoritma, toplamsal kombinatorikten sonuçlar kullanarak her girdi için bu tür yüksek boyutlu koordinatlar kuruyor. “Dolu” bölgenin içinde cevaplar bedavaya geliyor. Yalnızca kenara yakın ince bir bölge gerçek iş gerektiriyor; algoritma onu daha küçük problemlere bölüp özyinelemeli olarak çözüyor. Her tur bu bölgeyi keskin biçimde daraltıyor ve yalnızca sabit sayıda yeni boyut ekleniyor.

İspat nasıl kuruldu

Makale bir “yapay zekâ uyarısı” ile açılıyor. Yazarlar ana ispat rotasını, problemin yoğun ve çok boyutlu sürümleri üzerine kendi son çalışmalarına dayanarak kendileri tasarladı. Ardından bu fikirleri eksiksiz matematiksel ispatlara dönüştürmek için bir yapay zekâ modeli olan GPT Astra Ultra’yı kullandılar. Model birkaç lemmada takıldı; bunlar yazarların fikirleriyle çözüldü; kamuya açık bir araştırma notu konuşmaları belgeliyor. Temel rastgele algoritma tamamlanınca model onu deterministik, çok boyutlu sürümlere “yazarlardan hiçbir yönlendirme almadan” genişletti. Model makalenin taslağını da yazdı ve yazarların ifadesine göre ana sonuçlarını Lean 4 ispat asistanında bir ispatla doğruladı. Yazarlar içeriğin tüm sorumluluğunu üstleniyor.

Henüz bitiş çizgisi değil

Üs tam olarak 1 değil 1 + ε ve ε küçüldükçe gizli sabitler büyüyor; boyut sayısına bağımlılık optimize edilmemiş. Yazarlar algoritmayı kendileri “oldukça karmaşık” olarak tanımlıyor. Makale kuramsal: hiçbir uygulama ya da kıyaslama testi raporlamıyor.