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

Olarak hesaplama karmaşıklığı teori , P olarak da bilinen ptime veya DTime ( n- O (1) ), bir temeldir karmaşıklık sınıfı . Bir polinom miktarı hesaplama zamanı veya polinom zamanı kullanan deterministik bir Turing makinesi tarafından çözülebilen tüm karar problemlerini içerir .

Cobham'ın tezi , P'nin "etkin bir şekilde çözülebilir" veya " izlenebilir " olan hesaplama problemlerinin sınıfı olduğunu savunuyor . Bu kesin değildir: pratikte, P'de olduğu bilinmeyen bazı problemlerin pratik çözümleri vardır ve bazılarının P'de yoktur, ancak bu yararlı bir temel kuraldır .

Tanım

Bir L dili , ancak ve ancak deterministik bir Turing makinesi M varsa , P'dedir ;

  • M , tüm girişlerde polinom zamanı için çalışır
  • L' deki tüm x için , M çıkışları 1
  • Tüm için x değil L , M 0 çıktılar

P aynı zamanda tek tip bir boolean devreleri ailesi olarak da görülebilir . Bir L dili , yalnızca ve ancak bir polinom zamanlı tek biçimli boolean devreleri ailesi varsa, P'dedir ;

  • Hepsi için , giriş olarak n bit alır ve 1 bit verir.
  • L' deki tüm x için ,
  • L'de olmayan tüm x için ,

Devre tanımı , karmaşıklık sınıfını değiştirmeden yalnızca bir logspace üniform ailesini kullanmak için zayıflatılabilir .

P'deki önemli sorunlar

P'nin doğrusal programlamanın karar versiyonları ve maksimum eşleşme bulma gibi birçok doğal problemi içerdiği bilinmektedir . 2002 yılında, bir numara olup olmadığını belirlerken problemi olduğu gösterilmiştir asal P. ise ilgili sınıf işlevi sorunlarına olan FP .

Değişen grafiklerde st -bağlanabilirlik (veya erişilebilirlik ) dahil olmak üzere P için çeşitli doğal problemler tamamlanmıştır . P-tamamlanmış problemler hakkındaki makale, P'deki diğer ilgili problemleri listeler.

Diğer sınıflarla ilişkiler

P Bir genelleme NP sınıfıdır, karar problemleri bir yan Karar verilebilen belirli olmayan Turing makinası içinde çalıştığı, polinom zamanda . Eşdeğer olarak, her "evet" örneğinin bir polinom boyutu sertifikasına sahip olduğu ve sertifikaların bir polinom zaman deterministik Turing makinesi tarafından kontrol edilebildiği karar problemleri sınıfıdır. Bunun "hayır" örnekleri için geçerli olduğu problem sınıfına co-NP adı verilir . P, önemsiz bir şekilde NP'nin ve ko-NP'nin bir alt kümesidir; Çoğu uzman bunun uygun bir alt küme olduğuna inanır, ancak bu ( hipotez ) kanıtlanmamıştır. Başka bir açık problem, NP = ko-NP olup olmadığıdır; P = co-P olduğundan, olumsuz bir cevap .

P'nin aynı zamanda, en az , logaritmik miktarda bellek alanı içinde karara bağlanabilen problemler sınıfı olan L kadar büyük olduğu da bilinmektedir . Alanı kullanan bir karar verici zamandan fazlasını kullanamaz , çünkü bu olası konfigürasyonların toplam sayısıdır; bu nedenle, L, P'nin bir alt kümesidir. Diğer bir önemli sorun, L = P olup olmadığıdır. P = AL olduğunu biliyoruz, alternatif Turing makineleriyle logaritmik bellekte çözülebilen problemler kümesi . P'nin ayrıca polinom uzayında karar verilebilir problemler sınıfı olan PSPACE'den daha büyük olmadığı da bilinmektedir . Yine, P = PSPACE açık bir problem olup olmadığı. Özetlemek:

Burada EXPTIME , üstel zamanda çözülebilen problemlerin sınıfıdır. Yukarıda gösterilen tüm sınıflardan sadece iki katı sınırlama bilinmektedir:

  • P kesinlikle EXPTIME'da bulunur. Sonuç olarak, tüm EXPTIME-zor problemler P'nin dışındadır ve yukarıdaki P'nin sağındaki sınırlamalardan en az biri katıdır (aslında, üçünün de katı olduğuna yaygın olarak inanılmaktadır).
  • L kesinlikle PSPACE'de bulunur.

P'deki en zor problemler P-tam problemlerdir.

P'nin başka bir genellemesi, P/poli veya Tek Biçimli Olmayan Polinom Zamanıdır. Bir problem P/poly'de ise, sadece girişin uzunluğuna bağlı bir tavsiye dizisi verilmesi şartıyla deterministik polinom zamanında çözülebilir . Ancak NP'den farklı olarak, polinom-zaman makinesinin hileli tavsiye dizilerini algılamasına gerek yoktur; doğrulayıcı değildir. P/poly, BPP'nin tamamı dahil olmak üzere neredeyse tüm pratik sorunları içeren büyük bir sınıftır . NP içeriyorsa, polinom hiyerarşisi ikinci seviyeye çöker. Öte yandan, aynı zamanda, karar verilemeyen herhangi bir problemin tekli versiyonu gibi bazı karar verilemeyen problemler de dahil olmak üzere bazı pratik olmayan problemler de içermektedir .

1999'da Jin-Yi Cai ve D. Sivakumar, Mitsunori Ogihara'nın çalışmalarına dayanarak, P-tamamlanmış seyrek bir dil varsa , o zaman L = P olduğunu gösterdi.

Özellikleri

Polinom zamanlı algoritmalar kompozisyon altında kapalıdır. Sezgisel olarak, bu, işlev çağrılarının sabit zamanlı olduğunu varsayarak polinom zamanlı bir işlev yazarsa ve işlevlerin kendileri polinom zaman gerektiriyorsa, tüm algoritmanın polinom zaman alacağını söyler. Bunun bir sonucu, P'nin kendisi için düşük olmasıdır. Bu aynı zamanda P'nin makineden bağımsız bir sınıf olarak görülmesinin ana nedenlerinden biridir; polinom zamanında simüle edilebilen rastgele erişim gibi herhangi bir makine "özelliği", onu daha temel bir makinede bir polinom zaman algoritmasına indirgemek için ana polinom zaman algoritması ile basitçe oluşturulabilir.

P'deki diller ayrıca ters çevirme, kesişme , birleşme , birleştirme , Kleene kapatma , ters homomorfizma ve tamamlama altında kapalıdır .

Polinom zamanlı algoritmaların saf varlık kanıtları

Bazı problemlerin polinom zamanında çözülebildiği bilinmektedir, ancak bunları çözmek için somut bir algoritma bilinmemektedir. Örneğin, Robertson–Seymour teoremi , (örneğin) bir simit üzerine yerleştirilebilecek bir grafik kümesini karakterize eden , yasaklanmış küçüklerin sonlu bir listesinin olduğunu garanti eder ; ayrıca, Robertson ve Seymour, bir grafiğin minör olarak verilen bir grafiği olup olmadığını belirlemek için bir O( n 3 ) algoritması olduğunu gösterdi . Bu , bu problem için bilinen somut bir algoritma olmamasına rağmen, belirli bir grafiğin bir simit üzerine gömülü olup olmayacağını belirlemek için bir polinom-zaman algoritması olduğuna dair yapıcı olmayan bir kanıt sağlar .

Alternatif karakterizasyonlar

Olarak açıklayıcı karmaşıklık sorunları içinde eksprese olarak, P tanımlanabilir FO (İGK) , birinci dereceden mantığı bir ile en az sabit nokta sıralı yapılar üzerinde kendisine eklenmiş operatörü. Immerman'ın 1999'daki tanımlayıcı karmaşıklık ders kitabında , Immerman bu sonucu Vardi'ye ve Immerman'a atfeder.

2001'de PTIME'ın (pozitif) aralık birleştirme gramerlerine karşılık geldiği yayınlandı .

Tarih

Kozen , Cobham ve Edmonds'un "genel olarak polinom zaman kavramının icadıyla itibar edildiğini" belirtir . Cobham, sınıfı verimli algoritmaları karakterize etmenin sağlam bir yolu olarak icat etti ve Cobham'ın tezine yol açtı . Bununla birlikte, HC Pocklington , 1910 tarihli bir makalesinde, ikinci dereceden eşleşmeleri çözmek için iki algoritmayı analiz etti ve birinin "modülün logaritmasının gücüyle orantılı" zaman aldığını gözlemledi ve bunu modülün kendisiyle "zaman orantılı" olanla karşılaştırdı. veya karekökü", böylece açıkça polinom zamanda çalışan bir algoritma ile çalışmayan bir algoritma arasında bir ayrım çizer.

Notlar

Referanslar

Dış bağlantılar