ZPP (karmaşıklık) - ZPP (complexity)
Olarak karmaşıklık teorisi , ZPP (sıfır hata olasılıksal polinom zaman ) olan karmaşıklığı sınıfı bir olan sorunların olasılık Turing makinesi bu özellikleri kullanılır:
- Her zaman doğru EVET veya HAYIR cevabını verir.
- Çalışma süresi, her girdi için beklenen polinomdur.
Başka bir deyişle, algoritmanın çalışırken gerçekten rastgele bir madeni parayı çevirmesine izin verilirse, her zaman doğru cevabı döndürür ve n büyüklüğündeki bir problem için , ortalama işleyen bir p ( n ) polinomu vardır. zaman, bazen çok daha uzun olsa bile, p ( n ) ' den daha az olacaktır . Böyle bir algoritmaya Las Vegas algoritması denir .
Alternatif olarak, ZPP , aşağıdaki özelliklere sahip olasılıklı bir Turing makinesinin var olduğu problemler sınıfı olarak tanımlanabilir :
- Her zaman polinom zamanda çalışır.
- EVET, HAYIR veya BİLMİYOR şeklinde yanıt verir.
- Cevap her zaman ya BİLMİYORUM ya da doğru cevaptır.
- Her girdi için en fazla 1/2 olasılıkla (ve aksi takdirde doğru cevap) BİLİNMEYİN döndürür.
İki tanım eşdeğerdir.
ZPP'nin tanımı olasılıklı Turing makinelerine dayanmaktadır, ancak netlik açısından, bunlara dayalı diğer karmaşıklık sınıflarının BPP ve RP'yi içerdiğini unutmayın . BQP sınıfı , rasgeleliğe sahip başka bir makineye dayanır: kuantum bilgisayar .
Kesişim tanımı
ZPP sınıfı , RP ve ortak RP sınıflarının kesişimine tam olarak eşittir . Bu genellikle ZPP'nin tanımı olarak alınır . İçinde her sorunun bu, ilk notu görüntülemek için hem RP ve eş-RP bir sahiptir Las Vegas algoritması aşağıdaki gibi:
- Hem RP algoritması A hem de (muhtemelen tamamen farklı) ortak RP algoritması B tarafından tanınan bir L dilimiz olduğunu varsayalım .
- Bir girdi verildiğinde, bir adım için girişte A'yı çalıştırın. EVET döndürürse, cevap EVET olmalıdır. Aksi takdirde, bir adım için girişte B'yi çalıştırın. HAYIR döndürürse, cevap HAYIR olmalıdır. Hiçbiri olmazsa, bu adımı tekrarlayın.
Sadece bir makinenin yanlış cevap verebileceğini ve makinenin her tekrar sırasında yanlış cevap verme şansının en fazla% 50 olduğunu unutmayın. Bu araçlar olduğunu ulaşma şansı k katlanarak yuvarlak ruh doktoru inci k gösteren, beklenen çalışma süresi polinomlarıdır. O Bu gösterileri RP kesiştiği ortak RP bulunan ZPP .
ZPP'nin RP ile kesişen ortak RP'de yer aldığını göstermek için, bir problemi çözmek için bir Las Vegas algoritmasına C sahip olduğumuzu varsayalım. Daha sonra aşağıdaki RP algoritmasını oluşturabiliriz:
- C'yi beklenen çalışma süresinin en az iki katı kadar çalıştırın. Bir cevap veriyorsa, o cevabı ver. Biz onu durdurmadan cevap vermezse HAYIR verin.
By Markov Eşitsizliği , bunu durdurmak önce bir cevap verecektir şans en az 1/2 olduğunu. Bu, bir YES örneğinde durdurarak ve HAYIR vererek yanlış cevap verme şansımızın RP algoritmasının tanımına uyacak şekilde en fazla 1/2 olduğu anlamına gelir . Eş-RP algoritması o EVET ise C "kez" verir haricinde, aynıdır.
Tanık ve kanıt
NP , RP ve ZPP sınıfları , bir kümedeki üyeliğin kanıtı olarak düşünülebilir.
Tanım: Bir X kümesi için doğrulayıcı V, aşağıdaki özelliklere sahip bir Turing makinesidir:
- Eğer X olan X daha sonra bir dizi vardır ağırlık şekilde V ( X , a ) kabul eder;
- Eğer x değil X tüm dizileri daha sonra, ağ , V ( x , a ) reddeder.
W dizesi üyeliğin kanıtı olarak düşünülebilir. Verimli bir şekilde doğrulanabilen ( V , polinom zamanlı deterministik bir Turing makinesidir) kısa ispatlar (girdinin boyutunda bir polinom ile sınırlanan uzunluk ) durumunda, w dizesine tanık denir .
Notlar:
- Tanım çok asimetriktir. X'in X'te olmasının kanıtı tek bir dizedir. X'in X'te olmadığının kanıtı, hiçbiri üyeliğin kanıtı olmayan tüm dizelerin toplamıdır.
- Tanığın mevcudiyeti tek tiptir. X'teki tüm x'ler için bir tanık olmalıdır. X'teki belirli x'in doğrulanmasının çok zor olduğu, oysa çoğunun olmadığı durum böyle değildir.
- Tanığın geleneksel olarak yorumlanmış bir kanıt olması gerekmez. Eğer V olasılıklı bir Turing makinesiyse ve eğer x X'in içindeyse x'i kabul edebiliyorsa, kanıt, makineyi şans, sezgi veya deha ile x'i kabul etmeye götüren yazı tura dizisidir .
- Ortak kavram, üye olmamanın veya tamamlayıcı kümedeki üyeliğin bir kanıtıdır.
NP , RP ve ZPP sınıfları , üyelik için tanıkların olduğu setlerdir . NP sınıfı , yalnızca tanıkların var olmasını gerektirir. Çok nadir olabilirler. F bir polinom içeren 2 f (| x |) olası dizgiden yalnızca birinin doğrulayıcının kabul etmesine neden olması gerekir (eğer x X'in içindeyse. X, X'te değilse, hiçbir dizge doğrulayıcının kabul etmesine neden olmaz).
RP ve ZPP sınıfları için rastgele seçilen herhangi bir dizge muhtemelen tanık olacaktır.
İlgili ortak sınıfların üye olmama için tanığı vardır. Özellikle, ortak RP , x'in X'te olmaması durumunda, rastgele seçilen herhangi bir dizenin üyelik olmama için bir tanık olma olasılığı bulunan kümeler sınıfıdır. ZPP , hangi durumda olursa olsun, herhangi bir rasgele dizgenin X'de x'in veya x'in X'te olmadığının bir tanığı olma olasılığı bulunan kümeler sınıfıdır.
Bu tanımı RP , ortak RP ve ZPP'nin diğer tanımlarıyla birleştirmek kolaydır. Olasılıklı polinom zamanlı Turing Makinesi V * w ( x ) , V * ' nin rasgele bandını, üzerine dizisinin yazıldığı V için ikinci bir giriş bandı ile değiştirerek deterministik polinom zamanlı Turing Makinesi V ( x , w )' ye karşılık gelir . bozuk para çevirir. Tanığı rastgele bir dizge olarak seçerek, doğrulayıcı, x'in X'te olduğu zaman x'i kabul etme olasılığı büyük (diyelim ki 1 / 2'den büyük), ancak x ∉ X ise sıfır olan ( RP için ); x, X içinde olmadığında x'in reddedilmesi büyüktür, ancak x ∈ X ise sıfırdır ( birlikte RP için ); ve x'i X'in bir üyesi olarak doğru bir şekilde kabul etmek veya reddetmek büyüktür, ancak x'i yanlış kabul etmek veya reddetmek ( ZPP için ) sıfırdır .
Olası bir tanığın tekrarlanan rasgele seçimiyle, rasgele bir dizinin tanık olma olasılığı, bir girdiyi kabul etmek veya reddetmek için beklenen bir polinom zaman algoritması verir. Tersine, Turing Makinesinden polinom zamanı bekleniyorsa (herhangi bir x için), bu durumda çalışmaların önemli bir kısmı polinom zamana bağlı olmalıdır ve böyle bir çalışmada kullanılan madeni para dizisi bir tanık olacaktır.
ZPP , BPP ile karşılaştırılmalıdır . BPP sınıfı , tanıkların yeterli olmasına rağmen tanık gerektirmez (bu nedenle BPP , RP , ortak RP ve ZPP içerir ). Bir BPP dil V (X, W) dizeleri (net) çoğunluğu kabul sahip g x X olan ve x değilse ağırlık tersine dizeleri (net) çoğunluğu reddetme durumunda X . Hiçbir dizginin kesin olması gerekmez ve bu nedenle bunlar genel olarak delil veya tanık olarak kabul edilemez.
Karmaşıklık-teorik özellikler
ZPP'nin tamamlayıcı altında kapalı olduğu bilinmektedir; yani, ZPP = co-ZPP.
ZPP kendi başına düşüktür , yani ZPP sorunlarını anında çözme gücüne sahip bir ZPP makinesi (bir ZPP oracle makinesi), bu ekstra güç olmadan makineden daha güçlü değildir. Sembollerde, ZPP ZPP = ZPP .
ZPP NP BPP = ZPP NP .
NP BPP , ZPP NP'de bulunur .
Diğer sınıflarla bağlantı
Yana ZPP = RP ∩ Corp , ZPP açıkça her iki içerdiği RP ve corp .
P sınıfı , ZPP'de bulunur ve bazı bilgisayar bilimcileri, P = ZPP , yani her Las Vegas algoritmasının deterministik bir polinom-zaman eşdeğeri olduğunu varsaymışlardır.
ZPP = EXPTIME olan bir oracle var . A kanıtı ZPP = EXPTIME geldiği anlamına geliyordu P ≠ ZPP olarak, P ≠ EXPTIME (bkz zaman hiyerarşi teoremini ).