Genelleştirilmiş coğrafya

In karmaşıklık teorisi , genelleştirilmiş coğrafya bir olan klasik Pspace -tamamlamak sorun . İngilizce Genelleştirilmiş Coğrafya adıyla daha iyi bilinir ve GG olarak kısaltılır.

Giriş

Başlangıçta, Coğrafya, iki oyuncunun sırayla farklı şehir isimlerini çağırdığı uzun araba yolculuklarına özellikle uygun bir oyundu. Verilen her şehir adı bir öncekinin son harfiyle başlamalıdır (serbestçe seçilen ilki hariç) ve daha önce kullanılmış bir şehir adı vermek yasaktır. Kısıtlamalara uyarak bir şehir adı veremeyen ilk oyuncu oyunu kaybeder ve oyun sona erer.

Grafik modelleme

Oyun , düğümleri dünyadaki şehirlerin adlarını temsil eden yönlendirilmiş bir grafikle temsil edilebilir. Bir ok, N 1 düğümünü N 2 düğümüne bağlar, ancak ve ancak düğüm N 2 tarafından temsil edilen şehir adı , düğüm N 1 tarafından temsil edilenin son harfiyle başlıyorsa . Diğer bir deyişle, bir ok, oyunun kurallarına göre bir şehirden diğerine geçmenin mümkün olduğunu temsil eder.Oyun, oyuncuların her birinin bir komşu düğümü seçtiği grafik üzerinde bir yürüyüşe karşılık gelir. ziyaret edilmemiş mevcut düğüm. Bunu yapamayan ilk oyuncu oyunu kaybeder. Michigan eyaletindeki (Birleşik Devletler) şehirlerin isimleriyle gösterilen bir örnek aşağıda gösterilmiştir.

Genelleştirilmiş coğrafya probleminde, basitçe, köşelerinden birinin başlangıç ​​köşesi olarak belirlendiği yönlendirilmiş bir grafiği ele alıyoruz (artık ilk şehri özgürce seçmiyoruz). Aşağıdaki grafik, GG sorununun örnek bir örneğini göstermektedir.

Oyun oyna

P 1'i ilk oynayan oyuncu ve P 2'yi ikinci oynayan oyuncu olarak tanımlarız . Ayrıca N 1 giriş noktası olan grafiğin düğümlerini N 1 ,…, N n olarak tanımlıyoruz . Oynanan bir oyun, N 1 düğümünden başlayarak aynı tepe noktasından asla iki kez geçmeyen maksimum yola karşılık gelir .

Hesaplama karmaşıklığı

Hangi oyuncunun (P 1 veya P 2 ) kazanan bir stratejiye sahip olduğunu bulmada bir G grafiği ve bir tepe N 1 verildiğinde oluşan GG sorunu , PSPACE tamamlandı.

Genelleştirilmiş Coğrafya PSPACE tamamlandı

GG, PSPACE tamamlandı. Bu, hem PSPACE hem de PSPACE zor olduğu anlamına gelir. Bu iki ifadeyi ayrı ayrı kanıtlıyoruz.

Genelleştirilmiş Coğrafya PSPACE'de.

Gösteri

GG = {<G, b> | P1, genelleştirilmiş coğrafya oyununun bir parçası olan köşe b'den başlayarak g grafiğinde kazanma stratejisine sahiptir. }. GG'nin PSPACE'de olduğunu, aşağıdaki polinom yürütme algoritmasını tanıtarak gösteriyoruz.

Giriş: <G, nstart>

1. Nstart'ın çıktı değerini ölçün. Bu arity 0 ise "kayıp" iade edilir.
2. Nstart'tan erişilebilen düğümlerin bir listesini oluşturun: L = n1, n2,…, ni.
3. G2'den nstart'ı ve ona bağlı olan tüm kenarları çıkararak G2'yi oluşturun.
4. L'deki her n için <G2, n> parametresine özyinelemeli bir çağrı yapın. Bu özyinelemeli çağrılar sıralı olarak yapılır. Bu nedenle, tüm özyinelemeli aramalar için yalnızca en pahalı aramanın hafıza ücretini ödüyoruz.
5. Tüm bu yinelemeli çağrılar "kazandı" döndürürse, "kaybedilen" dönüşü (rakibi P1 ne yaparsa yapsın). Aksi takdirde "kazandı" döndürür.

Algoritma, GG'ye açıkça karar verir. Ayrıca, n'lik bir maksimum özyineleme derinliğine sahibiz ve her özyineleme adımının bellek maliyeti, girişin boyutuna göre doğrusaldır. Bu nedenle tüketilen bellek, girişin boyutunda gerçekten de polinomdur. GG, PSPACE içinde.

Genelleştirilmiş coğrafya PSPACE açısından zordur.

Gösteri

Aşağıdaki kanıt, David Liechtenstein ve Michael Sipser'den kaynaklanmaktadır.

FORMULA-GAME'i polinom zamanında GG'ye indirgeyerek GG'nin zor PSPACE olduğunu belirleyeceğiz (FORMULA-GAME'in kendisinin zor PSPACE olduğunu biliyoruz). FORMULA-GAME'in bir örneği nicelleştirilmiş bir Boole formülünden oluşur (kapanış) φ = ∃ x 1 ∀ x 2 ∃ x 3 … Qx k (ψ) burada Q ya ∃ veya ∀ (nicelik belirteçleri ∃ ve ∀ arasında değişim ile). İki PE ve PA oyuncusu, nicelik sırasına göre değişkenlerin değerlerini art arda seçerek rekabet eder. PE, ∃ ile ölçülen değişkenlerin değerini seçer ve PA diğerlerini seçer. Ψ'nın 3 büyüklüğündeki tümceciklerle birlikte normal formda olduğunu varsayıyoruz. PE, ancak ve ancak tüm nicelleştirmelerden sonra formül doğruysa kazanır.

FORMULA-GAME'in bir örneği ψ olsun.

Genelliği kaybetmeden, ilk ve son niceleyicilerin ∃ olduğunu varsayıyoruz. Ψ'de görünmeyen gereksiz değişkenler ekleyerek bu duruma her zaman geri dönebiliriz.

FORMULA-GAME örneğimizi, yukarıdaki diyagramda gösterilen ilkeye göre bir GG örneğine indirgiyoruz. Optimal P1 stratejisi PE'nin stratejisine ve P2'nin PA stratejisine karşılık gelecektir.

Sol dikey dize, değişkenlerin değerlerini seçme sürecine karşılık gelir. Her bir elmas mini yapıda sol veya sağ yolun seçimi, bir değişkenin değerinin seçimine karşılık gelir. İlk niceleyici bir ∃ olduğundan, PE önce oynar. PE, kantifikasyonlara ∃ karşılık gelen elmasların başında ve diğerlerinin başında PA oynamalıdır. Son niceleyici evrensel olduğundan, son elmastan çıktığımızda P1'in oynama sırası gelir (PE'ye karşılık gelir). P1 oyunu c'ye getirir, sonra oynamak P2'ye kalır.

FORMULA-GAME'de bu aşamada PE'nin formül doğruysa kazanacağını ve yanlışsa PA'nın kazanacağını unutmayın.

Formül yanlışsa (değerleme yapılan yol seçimlerine karşılık gelirse), P2'nin tatminsiz bir cümleye götüren bir yol seçmesi yeterlidir. Öyleyse P1 sadece "yanlış" olarak değerlendirilen bir kelimeye götüren yolu seçebilecek ve bu nedenle oyunu kazanan P2'ye son bir darbe bırakacaktır. Öyleyse, FORMULA-GAME örneğinde PA kazanırsa, P2 GG örneğimizde kazanır.

Benzer şekilde, formül doğruysa, P2 ne seçerse seçsin, P1'i bir "gerçek" cümlecik haline getirmiştir. İkincisi, bu nedenle, gerçek değerde gerçek değerine götüren bir yol seçebilir ve oyunu kazanır. Öyleyse FORMULA-GAME örneğinde PE kazanırsa, GG örneğimizde P1 kazanır.

Verilen FORMULA-GAME örneğini bir polinom süreci ile bir GG örneğine indirgedik.

Yani GG zor bir PSPACE.

Düzlemsel GG

Düzlemsel grafiklerle (Düzlemsel GG) sınırlı GG sorunu her zaman PSPACE tamamlanmıştır. Aşağıdaki kanıt, Teorem 3'ten gelir.

Gösteri

GG, PSPACE olduğundan ve düzlemsel GG, GG'nin örnekleri kısıtlanarak elde edildiğinden, düzlemsel GG, PSPACE içindedir. Hala Planar GG'nin zor bir PSPACE olduğunu kanıtlamamız gerekiyor. FORMULA-GAME'yi GG aracılığıyla Planar GG'ye düşürerek bunu kanıtlıyoruz.

Halihazırda bir GG örneğine indirgediğimiz bir FORMULA-GAME örneğinden başlayarak, grafiği üç kenarın bir noktada asla kesişmemesi ve kesişen iki kenarın aynı kısımda asla kullanılmaması için çizeriz. Bu genel olarak mümkün değildir, ancak FORMULA-GAME'in daha önce tarif ettiğimiz GG'ye indirgenmesiyle elde edilen grafiklerde böyle olur. Daha sonra her bir kesişme noktasını aşağıdaki diyagramda gösterilen yapı ile değiştiriyoruz.

Sonuç gerçekten de düzlemsel bir grafiktir. Olası durumların basit bir incelemesi, bu kesişen yapıyı çok az hamlede kaybetmeden ödünç aldığında "dönmenin" mümkün olmadığını göstermektedir. Ayrıca bu yapıdan çıktığınızda oynamak için iyi bir oyuncu.

Bu şekilde elde edilen yeni grafikte mükemmel oynanan bir oyun, bu nedenle FORMULA-GAME'den indirgeme çıktısında elde edilen grafikle aynı sonuca sahip olacaktır.

Bu indirgeme açıkça polinomdur. Planar GG bu nedenle tam PSPACE'dir.

Maksimum boşluk 3'ün iki taraflı düzlemsel grafikleri

Maksimal yön 3'ün iki taraflı düzlemsel grafikleriyle sınırlı problem her zaman PSPACE açısından zordur. Bunu kesinlikle üçten büyük kavşak köşelerini köşe zincirleriyle değiştirerek kanıtlıyoruz.

Edge Coğrafyası

Kenar Coğrafyası (Coğrafya kenarı tarafından çevrilebilir) adında bir GG çeşidi vardır; burada, her vuruştan sonra, daha önce kullanılmış olan ancak aynı düğümden birkaç kez geçebileceğimiz kenarı siliyoruz. Bu, her adımda ödünç alınan zirvelerin silinmesi olarak görülebilen GG ile tezat oluşturuyor. Bu nedenle GG'nin “Coğrafya Zirvesi” (Edge Geography) olduğunu düşünebiliriz.

Edge Geography ayrıca PSPACE ile tamamlanmıştır. Bu, nicelleştirilmiş Boole formüllerini Edge Geography örneklerine indirgeyerek kanıtlanmıştır.

Yönsüz grafik

Yönlendirilmemiş grafiklere dayalı bir GG varyantını düşünebiliriz. Fraenkel, Scheinerman ve Ullman yönlendirilmemiş Kenar Coğrafya içinde olduğunu göstermiştir P yönlendirilmemiş GG biz kısıtlarsanız biz maksimal Arity 3. düzlemi grafikleri kendimizi kısıtlamak bile, Pspace tamamlama iken kendimizi için ikili grafikler , sorun çözülebilir polinom zamanı.

Referanslar

1. David Lichtenstein ve Michael Sipser , "  Go Is Polinomial -Space Hard,  " Journal of the ACM , cilt.  27, n o  2Nisan 1980, s.  393–401 ( DOI  10.1145 / 322186.322201 , çevrimiçi okuyun )
2. Thomas J. Schaefer , "  İki kişilik mükemmel bilgi oyunlarının karmaşıklığı hakkında  ", Journal of Computer and System Sciences , cilt.  16, n o  21978, s.  185–225 ( DOI  10.1016 / 0022-0000 (78) 90045-4 )
3. Aviezri Fraenkel , Edward Scheinerman ve Daniel Ullman , "  Yönlendirilmemiş uç coğrafya  ", Teorik Bilgisayar Bilimi , cilt.  112, n o  21993, s.  371–381 ( DOI  10.1016 / 0304-3975 (93) 90026-p )

• Michael Sipser, Hesaplama Teorisine Giriş , PWS, 1997.
• David Liechtenstein ve Michael Sipser, GO polinomiyal Space Hard'dır, Bilgisayar Makineleri Derneği Dergisi, Nisan 1980. [1] [2]
• Aynı sorunun İngilizce wikipedia sayfası .