Üstel Zaman Hipotezi (ETH)

Bazı problemleri ancak neredeyse bütün olasılıkları deneyerek çözebiliyoruz. İngilizcesi Exponential Time Hypothesis, kısaltması ETH olan üstel zaman hipotezi, bilgisayar bilimcilerinin belirli bir problem için ne kadar zeki olursak olalım başka bir yolu olmayacağına dair girdiği bir bahistir. Daha hızlı yöntemler vardır, ama en iyileri bile problemin büyüklüğüyle üstel olarak artan sayıda adıma ihtiyaç duyacaktır.

ETH, ayrı bir makalede ele aldığımız P’ye karşı NP problemiyle yakından ilişkilidir. O makaleyi okumadıysan önce ona bir göz at, çünkü onun üzerine inşa edeceğiz. Özellikle bir algoritmanın karmaşıklığının ne olduğu ve n² ile 2ⁿ arasında neden bu kadar büyük bir uçurum bulunduğu üzerine.

Partiye Kimi Davet Etmeli?

Bir parti hazırlıyorsun ve dört arkadaşını davet etmek istiyorsun: Tolga, Jale, Kübra ve Doğan. İşin zor yanı, aralarında türlü türlü ilişkiler olması ve senin herkesin memnun kalmasını istemen. Uzun uzun sorup soruşturduktan sonra altı koşul ortaya çıkıyor:

1. Tolga ya da Kübra gelir (ikisi birden de gelebilir).
2. Jale ile Kübra birbirini çekemez, bu yüzden ikisi birden gelmez.
3. Doğan yalnızca Jale de gelirse gelir.
4. Tolga gelirse Kübra ya da Doğan da gelmelidir.
5. Tolga ile Kübra ikisi birden gelirse Jale de gelmelidir.
6. Tolga, Jale ve Doğan üçlüsünden en az biri gelir.

Bütün koşulların aynı anda sağlanması için kimi davet etmelisin? Kendin bulmaya çalış; çözümü makalenin sonuna sakladık.

Bilgisayar bilimcileri bu problemi önermeler mantığının diline çevirirdi. Her arkadaş bir harf alır, örneğin Tolga için T. Harf ya doğrudur (Tolga gelir) ya da yanlıştır (Tolga gelmez). ∨ sembolü “veya”, ¬ sembolü “değil” diye okunur. Bu durumda birinci koşul şöyle görünür:

$$T\vee K$$

İkinci koşul, Jale’nin gelmediğini veya Kübra’nın gelmediğini söyler:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Üçüncü koşulda kolayca yanılabilirsin. “Doğan yalnızca Jale de gelirse gelir” demek, Doğan’ın gelip Jale’nin gelmemesinin olmaması gerektiği anlamına gelir. Yani ya Doğan gelmez ya da Jale gelir:

$$\mathrm{\neg }D\vee J$$

Geri kalanları da aynı şekilde yazarız. Bütün problem şöyle görünür:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Koşulların birbirine ne kadar benzediğine dikkat et: birkaç harf, bazılarının önünde ¬ işareti, hepsi “veya” sözcüğüyle bağlanmış. Ve hiçbirinde üçten fazla harf yok. Böyle koşulların verildiği ve hepsinin aynı anda sağlanması için harflere doğru ve yanlış değerlerinin nasıl atanacağının arandığı probleme 3-SAT denir. Üç, bir koşulda en fazla üç harf bulunduğunu gösterir; SAT ise İngilizce satisfiability, yani sağlanabilirlik sözcüğünün kısaltmasıdır.

İlk bakışta bulmaca köşesine yakışan bir oyun gibi görünüyor. Oysa çok sayıda pratik problem 3-SAT biçiminde yazılabilir: ders programları, bir işlemci yongasının doğru hesap yapıp yapmadığının denetlenmesi, vardiya planlaması, hatta sudoku. O zaman harf sayısı dört değil, rahatlıkla milyonlarca olur.

Kaç Olasılığı Denemek Gerekir?

En dolaysız yöntem her şeyi denemektir. Tolga gelir ya da gelmez; bu iki olasılık eder. Bunların her biri için Jale gelir ya da gelmez; bu da dört olasılık eder. Dört arkadaş için olasılık sayısı şudur:

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

Aynı akıl yürütmeyi P’ye karşı NP makalesinde ikili vektörlerde de yapmıştık. n harfimiz varsa onlara doğru ve yanlış değerlerini 2ⁿ farklı şekilde atayabiliriz. 4 arkadaş için bu, birkaç dakikada gözden geçirebileceğin 16 olasılıktır. 100 harf için ise

$$2^{100}\approx 1,27\cdot {10}^{30}$$

olasılık vardır. Saniyede bir milyar olasılık deneyen bir bilgisayar, evrenin var olduğu sürenin yaklaşık üç bin katı kadar zamana ihtiyaç duyardı.

Ama tersi kolaydır: Biri sana “şu üçünü davet et” derse bunu hemen doğrularsın. Altı koşulu tek tek gözden geçirip her birinin sağlanıp sağlanmadığına bakman yeterlidir. Çözümü bulmak zor, kontrol etmek kolaydır. P’ye karşı NP makalesinde tam olarak bu tür problemleri NP sınıfına koymuştuk.

Ancak 3-SAT, NP içinde sıradan bir problem değildir: 1971’de NP’deki her problemin 3-SAT’a çevrilebileceği gösterildi. Dolayısıyla 3-SAT’ı hızlı çözebilen biri, hızlı doğrulanabilen her şeyi hızlı çözebilirdi. Bu özelliğe sahip problemlere NP-tam problemler denir ve 3-SAT bunların en ünlü temsilcisidir.

2ⁿ’den Daha Hızlı Olabilir mi?

Evet. Her şeyi tek tek denemek gereksiz. Örneğin şunu fark etmek yeter: Tolga gelmezse birinci koşuldan hemen Kübra’nın gelmesi gerektiği çıkar. İkisinin de gelmediği bütün olasılıkları doğrudan eleriz. Akıllı algoritmalar bu tür pek çok hileyi bir araya getirir. Bugün bilinen en iyileri yaklaşık

$${\mathrm{1,307}}^n$$

adıma ihtiyaç duyar. Bu çok büyük bir sıçrama. n = 100 için 10³⁰ yerine yaklaşık 4,2 · 10¹¹ adım çıkar; bir bilgisayar bunu birkaç dakikada yapar.

Ama dikkat, işin bir de kötü tarafı var. 1,307ⁿ yine de bir üstel fonksiyondur. Tabanı ikiden 1,307’ye düşürdük ama n değişkeni üs olarak kaldı. n büyümeye devam ettikçe sonunda yine de bizi ezip geçecek. n = 1000 için 1,307ⁿ bile 117 basamaklı bir sayıdır.

Peki üstel olmayan bir algoritma nasıl olurdu? Örneğin n³ adımla yetinen bir algoritma. Böyle bir algoritma polinom zamanlı olurdu ve 3-SAT o zaman P sınıfına ait olurdu. Ancak polinomlarla üstel fonksiyonlar arasında bir gri bölge daha vardır: her polinomdan daha hızlı, ama yine de her üstel fonksiyondan daha yavaş büyüyen fonksiyonlar. Örneğin

$$2^{\sqrt{n}}.$$

Burada üs yalnızca n’nin kareköküdür. Dört fonksiyonu bir tabloda karşılaştıralım:

n = 1000 için $2^{\sqrt{n}}$, n³ ile aynı ligde oynarken iki üstel fonksiyon adı bile olmayan sayılara fırlamıştır. $2^{\sqrt{n}}$ gibi, birden büyük her c tabanı için cⁿ’den daha yavaş büyüyen fonksiyonlara alt üstel fonksiyonlar denir.

Aynı şeyi grafik de gösteriyor. Dikey eksen logaritmiktir: yukarı doğru her bölme, yüz bin kat daha büyük bir sayı demektir. Aksi hâlde şekle 2ⁿ’den başka hiçbir şey sığmazdı.

Böyle bir grafikte üstel fonksiyonlar durmadan yükselen doğrulardır. Kırmızı 2ⁿ, turuncu 1,307ⁿ’den daha diktir ama ikisi de doğrudur. İlginç olan, turuncunun başta yeşil n³’ün bile altında kalmasıdır. Onu ancak n = 42 civarında geçer, ama ondan sonra kalıcı olarak. Mavi $2^{\sqrt{n}}$ ise bükülür ve aşağıda, yeşilin yakınında kalır.

ETH Tam Olarak Ne Söylüyor?

Artık hipotezi ifade edebiliriz. Hipotezi 1999’da Russell Impagliazzo ve Ramamohan Paturi formüle etti:

Birden büyük öyle bir c sayısı vardır ki hiçbir algoritma n harfli 3-SAT’ı yaklaşık cⁿ adımdan daha hızlı çözemez.

Peki sade bir dille? Üstel fonksiyonun tabanını akıllıca hilelerle küçültebiliyoruz: ikiden 1,5’e, 1,307’ye, belki bir gün 1,2’ye. Ama onu hiçbir zaman bire istediğimiz kadar yaklaştıramayacağız. Bir yerde, altına inilemeyen bir sınır var. Dolayısıyla ETH’ye göre karmaşıklığı $2^{\sqrt{n}}$ olan bir algoritma var olmamalı.

Neden hipotez? Çünkü kimse onu ispatlayamıyor. ETH bir çalışma varsayımıdır; tıpkı P’ye karşı NP makalesinde P ≠ NP olduğunu varsaydığımız gibi. Bilgisayar bilimcilerinin çoğu ETH’ye inanır, çünkü onlarca yıllık çaba yalnızca tabanın ikiden aşağıya yavaş yavaş inmesini sağladı. Ama elinde bir ispat olan kimse yok.

ETH ve P’ye Karşı NP

Bu iki soru birbiriyle nasıl ilişkili? 3-SAT’ın “gerçek” bir zorluğu, yani mümkün olan en hızlı algoritması olduğunu düşün. Bu algoritma üç bölgeden birinde olabilir:

• Yeşil bölge, polinom. 3-SAT örneğin n³ adımda çözülebilir. 3-SAT NP-tam olduğundan bu durumda P = NP olurdu ve ETH elbette geçerli olmazdı.
• Mavi bölge, alt üstel. 3-SAT $2^{\sqrt{n}}$ adımda ya da buna benzer bir sürede çözülebilir. Polinom zamanda çözülemez, dolayısıyla P ≠ NP geçerlidir. Ama ETH geçerli olmazdı.
• Kırmızı bölge, üstel. cⁿ’den daha iyisi mümkün değildir. ETH geçerlidir ve bu nedenle P ≠ NP de geçerlidir.

Şekilden ETH’nin P ≠ NP’den daha güçlü bir iddia olduğu görülüyor. ETH yalnızca 3-SAT’ın polinom zamanda çözülemeyeceğini değil, alt üstel zamanda da çözülemeyeceğini söyler. ETH’yi ispatlayan kişi böylece P ≠ NP’yi de ispatlamış olur ve bir milyon dolar kazanır.

Tersine, ETH’yi çürüten kişinin bununla P = NP’yi de ispatlamış olması gerekmez. Ona mavi bölgeden bir algoritma yeter. Bunu aklında tut, birazdan kullanacağız.

ETH Ne İşe Yarar?

Bir problemin hızlı çözülemeyeceğini ispatlamak bilgisayar biliminde inanılmaz derecede zordur. Bunu neredeyse hiç yapamıyoruz. ETH bize bir arka kapı sunar: “X problemi zordur” yerine “ETH geçerliyse X problemi zordur” ifadesini ispatlarız.

Nasıl? X problemi hızlı çözülebilseydi 3-SAT’ın da hızlı çözülebileceğini gösteririz. Örneğin şu problemi ele alalım: n kişi var ve bazı ikililerin birbirini çekemediğini biliyoruz. Bu kişileri, böyle hiçbir ikili aynı odaya düşmeyecek şekilde üç odaya dağıtmak istiyoruz. Bilgisayar bilimcileri buna bir grafın üç renkle boyanması der. Her 3-SAT probleminden, kişi sayısı harf sayısının yalnızca birkaç katı olacak şekilde böyle bir problem kurulabilir. Dolayısıyla kişileri odalara alt üstel zamanda dağıtmak mümkün olsaydı, 3-SAT da alt üstel zamanda çözülebilirdi ve ETH çökerdi.

Bugün bu tür koşullu sonuçlardan yüzlercesi var. Tek tek problemlerin tam olarak ne kadar zor olduğunu inceleyen koca bir alan, temelleri üzerinde duran bir ev gibi ETH’nin üzerinde durur.

ETH’nin daha güçlü bir kardeşi de var: güçlü üstel zaman hipotezi (SETH). Bu hipotez, koşulların üçten fazla, örneğin on ya da yüz harf içerebildiği problemlere odaklanır. SETH, ne kadar uzun koşullara izin verirsek mümkün olan en iyi tabanın ikiye o kadar yaklaştığını öne sürer. Dolayısıyla uzun koşullarda, 2ⁿ olasılığın hepsini kaba kuvvetle denemeye kıyasla neredeyse hiçbir kazanç sağlanamazdı.

ETH’den Neden Şimdi Söz Ediliyor?

Özellikle ChatGPT sayesinde tanıdığın OpenAI şirketi, Ekim 2026’da bir ön baskı, yani henüz hakem değerlendirmesinden geçmemiş bir makale yayımladı. Makalenin adı The Exponential Time Hypothesis is False, Türkçesiyle “Üstel Zaman Hipotezi Yanlıştır”. Şirket bu makalede 3-SAT’ı yaklaşık

$$2^{\frac{n}{\sqrt{\ln n}}}$$

adımda çözen bir algoritma bulduğunu iddia ediyor. Yani üs tek başına n değil, (doğal) logaritmanın kareköküne bölünmüş n’dir. Bu payda korkunç derecede yavaş büyür ama büyür ve bu, fonksiyonun alt üstel olması için yeterlidir. Söylendiğine göre algoritma yalnızca tek bir çözüm bulmakla kalmıyor, kaç çözüm olduğunu da sayabiliyor.

Bu doğru olsaydı OpenAI’ın algoritması yukarıdaki şeklin mavi bölgesine düşerdi. Peki bu ne anlama gelirdi?

• ETH çökerdi; onunla birlikte SETH ve bu ikisine dayanan yüzlerce koşullu sonuç da. Bilgisayar bilimcileri “ETH geçerliyse o hâlde…” diye başlayan pek çok sonucu ya atmak ya da yeniden yazmak zorunda kalırdı.
• P’ye karşı NP problemi bununla çözülmüş olmazdı. Algoritma hâlâ polinom zamanlı değil.
• Pratikte neredeyse hiçbir şey değişmezdi. Formülde değerini bilmediğimiz sabitler gizli. Bunlar bire eşit olsaydı, n = 1000 için $\sqrt{\ln n}$ yaklaşık 2,6 çıkar ve yaklaşık 2³⁸⁰ adım elde ederdik. Bu, bugünkü en iyi algoritmaların 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ değeriyle neredeyse aynıdır. Yeni algoritma bugünkü algoritmaları ancak daha da büyük n değerleri için belirgin biçimde geride bırakırdı ve farkın ne kadar olacağı tam da bilinmeyen sabitlere bağlı. Dolayısıyla bu sonucun önemi daha çok teoriktir. Şifrelemeyi de bankacılığı da etkilemez.

Şu an için bu doğrulanmamış bir iddia. İspat uzun ve teknik; uzmanlar onu okumaya daha yeni başlıyor. Çözülmüş problemlerle ilgili büyük duyuruların yanlış çıktığı geçmişte pek çok kez görüldü; bu yüzden şimdilik uzmanların ne diyeceğini bekleyelim. Bu paragrafı 27 Ekim 2026’da yazıyoruz.

Parti Probleminin Çözümü

Tolga’yı, Jale’yi ve Doğan’ı davet etmelisin, Kübra’yı değil. Şekilde 16 olasılığın hepsi görülüyor. Her sütunda bir olasılık var: dolu daire arkadaşın geleceğini, boş daire gelmeyeceğini gösterir. Sütunun altındaki kırmızı sayı, sağlanmayan ilk koşulu gösterir. Bütün koşulların sağlandığı tek olasılık yeşil çerçeveyle işaretlenmiştir.

İşte ETH’nin neredeyse aşılmaz saydığı kaba kuvvet tam olarak budur: dört arkadaş için on altı sütun, yüz arkadaş için vücudumuzdaki atomlardan daha fazla sütun.

Ayrıca Bak

• Bilişimin En Büyük Problemi: P’ye Karşı NP
• Önermeler Mantığı
• Üstel Fonksiyon
• Üstel Artış