Bilişim ve yapay zekâÖn baskıTeori3 dk okuma

DEV RUBİK KÜPLERİNDE 10⁴⁰'LIK SABİT 30,5'E İNDİRİLDİ

Daha yeni 50 yaşını dolduran Rubik küpü belki de dünyanın en tanınmış bulmacası ve temel sorularından birini ifade etmek basit: En kötü durumda, onu çözmek kaç hamle alır? Klasik 3×3×3 küp için yanıt tam olarak biliniyor: 20 hamle; bu sonuç 2014’te, bu yeni makalenin yazarlarından Tomas Rokicki’nin de aralarında bulunduğu bir ekip tarafından yayımlandı.

Her kenarında n katman bulunan daha büyük küpler için kesin yanıt erişilemez durumda — belirli bir n×n×n küpü en iyi biçimde (optimal olarak) çözmek NP-tam bile. Ama 2011’de Erik Demaine ve meslektaşları en kötü durumun nasıl büyüdüğünü gösterdi: n² / lg n ile orantılı olarak; burada lg, 2 tabanında logaritmadır. Bu, parçaları esasen birer birer çözen standart yöntemlerden logaritmik bir çarpan kadar daha iyi.

Saçma bir sabite sahip bir kanıt

Bir sorun vardı. 2011 sonucu büyüme hızını garanti ediyordu, önündeki sayıyı değil. O algoritmayı adım adım inceleyen yazarlar, sabitinin yaklaşık 1,01 × 10⁴⁰ olduğunu buluyor. Suçlu, belirli hamlelerin 24 parçalık bir grubun her dizilişine ulaşabildiğini kanıtlayan, ama ne kadar çabuk ulaşabildiğini söylemeyen bir bilgisayar denetimi. Bu uzunluk için tek güvenli sınır, bu dizilişler grubunun büyüklüğüydü, yaklaşık 3,1 × 10²³ adım; formül de sonunda dev 24! sayısını (1 × 2 × … × 24, yaklaşık 6,2 × 10²³) iki yerde kullanıyor. Buna karşılık alt sınırın — karıştırılmış küplerin neredeyse hepsinin ihtiyaç duyduğu hamle sayısının — sabiti yaklaşık 12,88 gibi mütevazı bir değer. Bu yüzden topluluktaki pek çok kişi, böyle bir algoritmanın makul boyutlar için asla pratik olamayacağına inanıyordu.

MIT, TU Münih ve Palo Alto’dan Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf ve Erik Demaine şimdi bu sabiti açık ve küçük hale getirdi.

Küp parçaları için sıralama ağları

Büyük bir küpte merkez parçaları baskındır: Sayıları n² gibi büyürken köşeler ve kenarlar yalnızca n ile orantılı terimler ekler. Merkez parçaları, yalnızca kendi aralarında yer değiştirebilen 24’lük ailelere ayrılır. Temel araç komütatör (commutator): A B A′ B′ biçiminde, neredeyse her şeyi yerinde bırakıp tek bir ailenin yalnızca üç parçasının yerini değiştiren bir dizi. Ekip, kullanılabilir 4.000 üçlü yer değiştirmenin hepsi için, her biri en fazla 12 hamle uzunluğunda hamle dizileri buldu.

Sayıyı iki fikir düşürüyor. Birincisi, aynı komütatör, satır ve sütunlardan oluşan bütün gruplar boyunca birçok aileye aynı anda uygulanabilir. İkincisi, her aileyi kendi başına çözmek yerine, her aile yer değiştirmelerden oluşan tek ve sabit bir evrensel diziyi izler ve ihtiyaç duymadığı yer değiştirmeleri basitçe atlar. Bir lemma her şeyi birbirine bağlıyor: L aşamalı evrensel bir dizi, L/2’lik bir baş sabit verir.

Bu diziyi kısaltmak için bilgisayar biliminin sıralama ağlarından (sorting networks), yani her girdiyi sıralayan sabit karşılaştırma örüntülerinden araçlar ödünç alınıyor. Altı girdili optimal bir sıralama ağı 96 aşama, dolayısıyla 48’lik bir sabit veriyor. 24 konumu önce 12’lik, sonra 4’lük gruplara bölen ve bilgisayar aramasıyla bulunan ağlar bunu 72 aşamaya (36) indiriyor. Son olarak, aynı anda üçten fazla parçayı karıştıran hamlelere izin vermek ve konumları farklı biçimde bölmek bunu 61 aşamaya indiriyor.

Otuz virgül beş

Teorem: Her n×n×n küp en fazla 30,5 n²/lg n hamlede, artı büyük n için ihmal edilebilir hale gelen terimlerle çözülebilir. Sabit 3,30 × 10³⁸ kattan fazla iyileşiyor ve alt sınırın 2,37 katı içinde kalıyor (30,5 / 12,88). Isınma olarak kullanılan düz n×n×1 versiyonunda sabit 12 ya da 18’den 1,5’e düşüyor.

256 katmanlı bir küpün çözümünden sekiz kare, açılmış yüzler ve küçük küpler olarak gösteriliyor; karışık gürültüden düz renklere.

Kenar başına 256 katmanlı bir küpün çözümünden eşit aralıklı sekiz kare: Karışık yüzler düz renklere dönüşüyor. — Şekil 1.1, Mrzyglocki ve ark. (2026), arXiv:2611.11018.

Algoritma, parça sayısıyla orantılı sürede çalışıyor ve yazarlar, dayandığı her ağı kapsamlı biçimde denetleyen betiklerle birlikte açık kaynaklı bir çözücü sunuyor. Kendi karşılaştırmaları, çözücünün yaklaşık n = 840’tan itibaren mevcut çözücülerin önüne geçtiğini gösteriyor; kenar başına 256 ve 65.536 katmanlı küplerin çözümlerini görselleştirdiler.

2,37 asimptotik bir ifade: Formülün küçük terimleri kesin olarak belirlenmiş değil, bu yüzden belirli bir küp için kesin bir hamle sayısı vermiyor. Yazarlar gelecekteki kazanımların, parçaları sıralama ağlarında gruplamanın başka yollarından ve daha iyi üçlü yer değiştirmelerden gelebileceğini öne sürüyor — ve aynı mekanizma başka dev bulmacaların ya da dört ve beş boyutlu hiperküplerin de üstesinden gelebilir.