RP (karmaşıklık) - RP (complexity)

Olarak hesaplama karmaşıklığı teori , polinom zaman randomize ( RP ) olan karmaşıklığı sınıfı bir olan sorunların olasılık Turing makinesi bu özellikleri kullanılır:

RP algoritması (1 çalıştırma)
Cevap üretildi
doğru
cevap
Evet Hayır
Evet ≥ 1/2 ≤ 1/2
Hayır 0 1
RP algoritması ( n çalışır)
Cevap üretildi
doğru
cevap
Evet Hayır
Evet ≥ 1 − 2 n ≤ 2 - n
Hayır 0 1
ortak RP algoritması (1 çalıştırma)
Cevap üretildi
doğru
cevap
Evet Hayır
Evet 1 0
Hayır ≤ 1/2 ≥ 1/2
  • Giriş boyutunda her zaman polinom zamanında çalışır
  • Doğru cevap HAYIR ise her zaman HAYIR döner.
  • Doğru cevap EVET ise, en az 1/2 olasılıkla EVET verir (aksi halde HAYIR verir).

Başka bir deyişle, algoritma çalışırken gerçekten rastgele bir parayı çevirmesine izin verilir. Algoritmanın EVET döndürebildiği tek durum, asıl cevabın EVET olması; bu nedenle algoritma sonlandırılır ve EVET verirse, doğru cevap kesinlikle EVET'tir; ancak, gerçek yanıttan bağımsız olarak algoritma HAYIR ile sonlandırılabilir . Yani algoritma HAYIR döndürüyorsa yanlış olabilir.

Bazı yazarlar bu sınıfa R adını verir, ancak bu ad daha çok özyinelemeli diller sınıfı için kullanılır .

Doğru cevap EVET ise ve algoritma, her çalıştırmanın sonucu diğerlerinden istatistiksel olarak bağımsız olacak şekilde n kez çalıştırılırsa , en az 1 - 2 - n olasılıkla en az bir kez EVET döndürür . Yani algoritma 100 kez çalıştırılırsa, her seferinde yanlış cevap verme olasılığı, kozmik ışınların algoritmayı çalıştıran bilgisayarın belleğini bozma olasılığından daha düşüktür. Bu anlamda, eğer bir rastgele sayı kaynağı mevcutsa, RP'deki çoğu algoritma oldukça pratiktir.

Tanımdaki 1/2 kesri keyfidir. 1/2, 1'den küçük herhangi bir sabit sıfırdan farklı olasılık ile değiştirilse bile, set RP tamamen aynı problemleri içerecektir; burada sabit, algoritmanın girdisinden bağımsız anlamına gelir.

Resmi tanımlama

Bir dil L olan RP olasılıksal Turing makinesi vardır, ancak ve ancak M , öyle ki

  • M , tüm girişlerde polinom zamanı için çalışır
  • Tüm için x de L , M daha olasılık daha sonra ile 1 çıktılar ya da 1/2 eşit
  • Tüm için x değil L , M 0 çıktılar

Alternatif olarak, RP yalnızca deterministik Turing makineleri kullanılarak tanımlanabilir. Bir dil L olan RP polinom vardır, ancak ve ancak p ve deterministik Turing makinesi M şekilde,

  • M , tüm girişlerde polinom zamanı için çalışır
  • L' deki tüm x'ler için , y uzunluğundaki p (| x |) dizelerinin tatmin edici kesri 1/ 2'den büyük veya eşittir
  • Tüm için x değil L , ve şeritler y uzunluğu p (| x |),

Bu tanımda, y dizisi , olasılıklı Turing makinesinin yapacağı rastgele yazı turalarının çıktısına karşılık gelir. Bazı uygulamalar için bu tanım, olasılıklı Turing makinelerinden bahsetmediği için tercih edilir.

İlgili karmaşıklık sınıfları

Rastgele karmaşıklık sınıflarının şeması
RP, PSPACE içinde P'yi genelleştiren diğer olasılıksal karmaşıklık sınıflarına ( ZPP , ortak RP, BPP , BQP , PP ) göre . Bu sınırlamalardan herhangi birinin katı olup olmadığı bilinmiyor.

RP'nin tanımı, bir EVET yanıtının her zaman doğru olduğunu ve bir EVET örneği bir HAYIR yanıtı verebileceğinden, bir HAYIR yanıtının yanlış olabileceğini söyler. Karmaşıklık sınıfı ortak RP , bir iltifattır, burada bir EVET yanıtı yanlış olabilirken HAYIR yanıtı her zaman doğrudur.

Sınıf BPP hem VAR ve NO örnekleri üzerinde yanlış cevap verebilir algoritmaları tarif eder ve bu nedenle hem de içerir RP ve ko-RP . RP ve ortak RP kümelerinin kesişimi ZPP olarak adlandırılır . RP'nin R olarak adlandırılabileceği gibi , bazı yazarlar ortak RP yerine ortak R adını kullanır .

P ve NP'ye bağlantı

Bilgisayar biliminde çözülmemiş problem :

P , NP'nin bir altkümesi olan RP'nin bir alt kümesidir. Benzer şekilde, P , ortak NP'nin bir alt kümesi olan ortak RP'nin bir alt kümesidir. Bu kapanımların katı olup olmadığı bilinmemektedir. Bununla birlikte, yaygın olarak inanılan P = BPP varsayımıdoğruysa, o zaman RP , co-RP ve P çöker (hepsi eşittir). Ek olarak varsayarsak o PNP , bu daha sonra ima RP kesinlikle bulunan NP . RP = ko-RP olup olmadığı veya RP'nin NP ile ko-NP'nin kesişiminin bir alt kümesiolupolmadığı bilinmemektedir, ancak bu P = BPP ile ima edilecektir.

Co-RP'deki şu anda P'de olduğu bilinmeyen bir problemin doğal bir örneği , tamsayılar üzerinden verilen çok değişkenli aritmetik ifadenin sıfır polinom olup olmadığına karar verme problemi olan Polinom Kimlik Testidir. Örneğin, x · xy · y − ( x + y )·( xy ) sıfır polinomdur, ancak x · x + y · y değildir.

RP'nin bazen kullanımı daha kolay olan alternatif bir karakterizasyonu , makinenin ancak ve ancak giriş boyutundan bağımsız olarak hesaplama yollarının en azından sabit bir kısmının kabul etmesi durumunda kabul ettiği, deterministik olmayan Turing makineleri tarafından tanınan problemler kümesidir . Öte yandan NP , yolların katlanarak küçük bir bölümünü oluşturabilecek yalnızca bir kabul eden yola ihtiyaç duyar. Bu karakterizasyon, RP'nin NP'nin bir alt kümesi olduğu gerçeğini açıkça ortaya koymaktadır .

Ayrıca bakınız

Referanslar

Dış bağlantılar