Tamamlayıcı (karmaşıklık)
In karmaşıklık teorisi (bir alan teorik bilgisayar bilimleri ), biz söz tamamlayıcı bir sınıf C, diller sınıfının dillerine tamamlayıcı kümesini belirlemek için, COC veya COC ifade. Bu operatör olarak yeni sınıflar dikkate yol açar eş-NP , tamlayanı NP .
Resmi tanımlama
Bir dili tamamlayıcı
Düşünün bir alfabe üzerinde dili ve , kelimelerin kümesi . Sonra tamamlayıcısı burada kaydetti olduğunu . Biz tamamlayıcısı söz konusu fark olduğunu .
L{\ displaystyle L}Σ{\ displaystyle \ Sigma}Σ∗{\ displaystyle \ Sigma ^ {*}}Σ{\ displaystyle \ Sigma}L{\ displaystyle L}L¯{\ displaystyle {\ bar {L}}}Σ∗∖L{\ displaystyle \ Sigma ^ {*} \ setminus L}L¯{\ displaystyle {\ bar {L}}}L{\ displaystyle L}
Bir dil sınıfının tamamlayıcısı
Daha sonra, tamamlayıcı eş-C, C sınıfı olalım: .
vsÖ-VS={U⊆Σ∗|U¯⊆VS}{\ displaystyle co {\ text {-}} C = \ {U \ subseteq \ Sigma ^ {*} | {\ bar {U}} \ subseteq C \}}
Turing makineleri açısından
Turing makinelerinin ve problemlerinin bakış açısına bakarsak , tamamlayıcı karar problemi , soruyu cevaplamak için "evet" ve "hayır" ı tersine çevirdiğimiz bir problemdir .
"Tamamlayıcı" operatörün özelliği (co-)
Diller açısından
- vsÖ-(vsÖ-VS)=VS{\ displaystyle co {\ text {-}} (co {\ text {-}} C) = C}
- VS⊆VS′⇒vsÖ-VS⊆vsÖ-VS′{\ displaystyle C \ subseteq C '\ Rightarrow co {\ text {-}} C \ subseteq co {\ text {-}} C'}
Makine seviyesinde
Deterministik sınıflar söz konusu olduğunda, sınıflar ve bunların tamamlayıcıları eşittir: Verilen yanıtları tersine çevirmek yeterlidir; bu, deterministik olmayan bir makine için geçerli değildir, çünkü kabul eden bir yolun varlığı, tüm yollar kabul ediyor.
Teoremler
Immerman-Szelepcsényi teoremi
Genel biçiminde, Immerman-Szelepcsényi teoremi eşitliği belirtir :
NSPACE(s(değil))=co-NSPACE(s(değil)){\ displaystyle {\ text {NSPACE}} (s (n)) = {\ text {co-NSPACE}} (s (n))}herhangi bir işlev için .
s(değil)≥günlükdeğil{\ displaystyle s (n) \ geq \ log n}
Özellikle NL = co-NL.
Açık sorunlar
Öyle varsayılıyor , ama bu asla gösterilmedi. Bu soru P = NP problemiyle şu şekilde bağlantılıdır: eğer P = NP ise NP = co-NP çünkü P = co-P.
vsÖ-DEĞİLP≠DEĞİLP{\ displaystyle co {\ text {-}} NP \ neq NP}
Kaynakça
Notlar ve referanslar
-
Sylvain Perifel , Algoritmik karmaşıklık , Elipsler ,2014, 432 s. ( ISBN 9782729886929 , çevrimiçi okuyun ) , böl. 2.2 ("Belirleyici olmayan zaman") s sayfa 61.
-
(in) Sanjeev Arora ve Boaz Barak , Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım , Cambridge University Press , 2009( ISBN 0-521-42426-7 ) , böl. 2.6.1 ("coNP")
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">