Subhash Khot, 2002 yılında Unique Games Varsayımını (UGC) tanıttı ve bu, hesaplamalı karmaşıklık teorisi için merkezi bir düzenleyici ilke oluşturdu [1]. Bu varsayım, benzersiz permütasyon kısıtlamaları altında bir ağdaki düğümlere renk atamayı içeren belirli bir kısıt tatmin problemi türünün, hafif bir şekilde bile yaklaşık olarak çözülmesinin NP-zor olup olmadığını sorar [1].
Eğer doğruysa, UGC, geniş bir pratik problem sınıfı için “yeterince iyi” bir çözüm bulmanın, mükemmel bir çözüm bulmak kadar hesaplamalı olarak zor olduğunu ima eder [2].
Unique Games’ın Mekaniği
Unique bir oyun, iki düğüm arasındaki her kenarın bir permütasyon zorladığı bir etiket örtüsü problemidir: bir düğümün rengi, komşusunun rengini benzersiz bir şekilde belirler [1].
Tatmin Edilebilirlik vs. Zorluk
Bir örnek tamamen tatmin edilebilir olduğunda, bir düğüm için bir renk seçip ağı boyunca yayarak geçerli bir renkleme verimli bir şekilde bulunabilir [1].
Zorluk, örnek tatmin edilemez olduğunda ortaya çıkar. Neredeyse tüm kısıtların tatmin edilebildiği örnekler ile neredeyse hiç birinin tatmin edilemediği örnekler arasındaki ayrımı yapmak, üstel zaman gerektirdiği görülmektedir [1].
Resmi Tanım
Varsayım, herhangi bir küçük ε, δ > 0 sabiti için, bu problemin (1−δ, ε)-boşluk versiyonunun NP-zor olmasını sağlayacak bir alfabe büyüklüğü k bulunduğunu söyler [1]. Bu, k modunda iki değişkenli lineer denklemler sistemi olan Max2Lin(k)’nin yaklaşık çözülemezliği olarak eşdeğer şekilde görülür [1].
Neden Yaklaşım Zorluğu Önemlidir
Çip yerleşimi, havayolu planlaması ve protein katlanması gibi birçok gerçek dünya optimizasyon görevi NP-zordur; bu da büyük örnekler için tam çözümlerin pratik olmadığı anlamına gelir [2].
Yaklaşım Sınırı
P vs NP varsayımı tam çözümlerin muhtemelen mümkün olmadığını öne sürerken, UGC birçok problem için yüksek kaliteli yaklaşımların bile mümkün olmadığını ima eder [2].
“Çapa” Etkisi
UGC, teorik bir çapa görevi görür. Doğru olduğu varsayıldığında, araştırmacıların tek bir adımla çok geniş bir kısıt tatmin problemi yelpazesi için sıkı yaklaşım‑zorluk sonuçları kanıtlamalarına olanak tanır [2]. Avi Wigderson, bunu “birçok yaklaşım problemini bağlayabileceğimiz bir çapa” olarak tanımlar [2].
Disiplinlerarası Etki
UGC’nun sonuçları teorik bilgisayar bilimlerinin ötesine geçerek çeşitli alanlara yayılır. Araştırmacılar, köpüklerin yapısı, metrik uzayların geometrisi ve oy sistemlerinin analizi üzerine sonuçlar elde etmişlerdir [2].
Ryan O’Donnell, varsayımı “birçok problemi daha basit ve temiz hâle getiren sihirli bir anahtar” olarak tanımlar ve bunun araştırmacıların bu problemlere yaklaşımını temelden değiştirdiğini belirtir [2]. Bu verimlilik, UGC’nin hesaplamalı zorluğun temel bir yapısal özelliğini yakaladığını gösterir [2].
Güncel Durum ve Gelecek Etkileri
2011 itibarıyla akademik topluluk, UGC’nin doğru mu yoksa yanlış mı olduğu konusunda yaklaşık olarak eşit bölünmüştü [1]. Kesin bir kanıt ya da çürütme ortaya çıkmadığından, varsayım hâlâ açık bir soru olarak kalmakta ve mevcut araştırma gündemlerini şekillendirmektedir [2].
Bir Kanıtın Etkisi
Bir kanıt, birçok yaklaşım problemi için kesin zorluk eşiklerini sağlayacaktır. Yarı‑deterministik programlama gevşemelerinin — “açıkça şüpheli” algoritmaların — tüm kısıt tatmin problemleri için optimal olduğunu doğrular [2].
Bir Çürütmenin Etkisi
Bir çürütme de aynı derecede dönüştürücü olur. Bilinen hiçbir teknikle benzemeyen temelden yeni bir yaklaşım algoritması icat edilmesini gerektirir ve araştırmacıları gerçek yaklaşılabilirlik sınırını yeniden tanımlamaya zorlar [2].
Sonuç ne olursa olsun, Richard Lipton, “sonunda yanlış olduğu gösterilsin ya da gösterilmesin, varsayımın parlaklığında pek bir değişiklik olmaz” diye gözlemlemiştir [2].
