Karmaşıklık sınıfı

Gelen teorik bilgisayar bilimleri ve daha doğrusu içinde karmaşıklık teorisi , bir karmaşıklık sınıf kümesidir algoritmik problemlere çözünürlüğü belli kaynağın aynı miktarda gerektirir.

Bir sınıf, genellikle bir M sayısal modelinde, R tipi bir miktar kaynak kullanılarak çözülebilen tüm problemlerin kümesi olarak tanımlanır; burada n , girdinin boyutudur. $O (f (n))$

En yaygın sınıflar, hesaplama süresi veya alan kısıtlamaları ile Turing makinelerinde tanımlananlardır . Örneğin P ve NP sınıflarından bahsedebiliriz .

Zaman ve uzay karmaşıklığı sınıflarının dört ailesi

Zaman ve mekan, deterministik veya deterministik olmayan makineler olmasına bağlı olarak, karmaşıklık sınıflarının dört ana ailesini ayırt edebiliriz:

ZAMAN [t (n)) Deterministik bir makinede t (n) büyüklük sırasına göre çözülebilen karar problemleri sınıfı . NTIME (t (n)) Deterministik olmayan bir makinede t (n) büyüklük sırasına göre çözülebilen karar problemleri sınıfı . UZAY (s (n)) Belirleyici bir makinede s (n) mertebesinde bir uzayın çözülmesi gereken karar problemleri sınıfı . NSPACE (s (n)) Belirleyici olmayan bir makinede s (n) mertebesinde bir uzayın çözülmesi gereken karar problemleri sınıfı .

Zaman içindeki sınıflar

Klasik zamanlardaki sınıflar:

P , polinom zamanında deterministik bir makine tarafından karar verilen problem sınıfı. Bu problemler genellikle verimli bir algoritmanın olduğu problemler olarak kabul edilir (bkz. Cobham'ın tezi );
NP , polinom zamanında deterministik olmayan bir makine tarafından kararlaştırılan problemler sınıfı (ve tamamlayıcı sınıf , co-NP );
EXPTIME , deterministik bir makine tarafından üstel zamanda karar verilen problemler sınıfı;
NEXPTIME , belirleyici olmayan bir makine tarafından üstel zamanda karar verilen problemler sınıfı.

Uzay sınıfları

Alan kısıtlamaları için klasik sınıflar şunlardır:

L , deterministik bir makinede logaritmik uzayda çözülebilen problemler sınıfı;
NL , deterministik olmayan bir makinede logaritmik uzayda çözülebilen problemler sınıfı;
PSPACE , deterministik bir makinede polinom uzayda çözülebilen problemler sınıfı. Aslında bu sınıf, Savitch teoremine göre NPSPACE'e eşittir ;
EXPSPACE , üstel uzayda çözülebilen problemler sınıfı. Bu sınıf, Savitch teoremine göre NEXPSPACE'e eşittir .

Diğer sınıflar

Diğer karmaşıklık sınıfları, aşağıdakiler gibi başka bir hesaplama modeli kullananları içerir:

Örneğin, paralel hesaplamayı modellemeyi ve daha düşük sınırları daha kolay elde etmeyi mümkün kılan NC ve P / poly sınıflarına sahip Boole devreleri ;
Olasılıklı Turing makinelerini kullanan ve özellikle ZPP , RP ve BPP sınıfları ile rastgele algoritmaları modellemeyi mümkün kılan olasılık modelleri ;
veya BQP gibi kuantum sınıfları , IP ( etkileşimli ispat sistemleri bağlamında ) veya PCP gibi kriptografiden kaynaklanan sınıflar …

Sınıf kapsamları

Eklentilerimiz var:

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE = NEXPSPACE ;
P ⊆ Co-NP ⊆ PSPACE .

Hiyerarşi teoremleri şunları sağlar:

NL ⊊ PSPACE ⊊ EXPSPACE ;
P ⊊ EXPTIME ( deterministik zaman hiyerarşi teoremi );
NP ⊊ NEXPTIME .

Öte yandan, daha güçlü kapanımlarda durumun ne olduğunu bugün bilmiyoruz.

C-tam veya C-zor problemler

Tanım

Let C olması (örneğin bir karmaşıklık sınıfı P , NP , Pspace , vs.). Sorunun C- difficile olduğunu söylerler, eğer bu problem en azından C'deki tüm problemler kadar zor ise . Bir Cı- -difficile sorun ait C olduğu söylenir Cı -Komple.

Resmi olarak, bir indirgeme kavramı tanımlarız: Π ve Π 'iki sorun olsun; tt bir azalma 'tt için (sınıfsal daha düşük olduğu da bilinir), belirli bir karmaşıklık bir algoritma (ya da bir makine) olduğu C tt bir örneğine tt bir örneğini transforme'. Dolayısıyla, Π'yi çözecek bir algoritmamız varsa, Π'yi nasıl çözeceğimizi de biliyoruz. Bu nedenle, indirgemenin karmaşıklığı dışında, Π'nin en az Π 'kadar çözülmesi zor olduğunu söyleyebiliriz.

Π daha sonra C için -difficult eğer herhangi bir sorun, tt 've C , Π' tt azaltır. C- difficile kavramı , azaltma için izin verilen karmaşıklık türüne göre değişebilir. Çoğu durumda, polinom indirgemeleri ile ilgileniriz , yani sadece bir boşluk ve gerçekleştirilecek bir polinom zamanı gerektiren indirimler . Ancak, örneğin P ve L sınıfları arasındaki bağlantıyı incelemek için, logaritmik boşluk kullananlar gibi diğer indirgeme türleriyle de ilgilenebiliriz.

İndirgeme ilişkisi olma dönüşlü ve geçişli , bir tanımlar ön sipariş problemleri üzerinde. Bu nedenle, onu genellikle ≤ sembolü ile belirtiriz: ', to' ye düşerse Π'≤Π var. Sembole kendimize izin verdiğimiz indirgeme türünü belirten bir harf ekleyebiliriz: örneğin genellikle Π'dan Π 'ye bir polinom indirgeme olduğu anlamına gelir . Sorunlar C -difficiles olan üst sınırlarının içinde C ve sorunlara C -complets olan başlıca unsurlar arasında C . $\ Pi \ leq _ {P} \ Pi '$

Örnekler

NP-tam problemler bu kavramın önemli bir özel durum vardır. Standart bir şekilde, yalnızca polinom indirgemelerine izin vererek tanımlanırlar , yani bir Π 'örneğinden Π örneğine geçişi hesaplayan algoritma polinomdur. Cook-Levin teoremi nedeniyle, Stephen Cook ve Leonid Levin , NP-tam problemi devletler olduğunu. Cook, özellikle SAT sorununun NP-tamamlandığını göstermiştir. Diğer birçok sorun daha sonra NP-bütünlüğü olarak ortaya çıktı.

Biz bahsederken P tamamlama ya P-zor problemler sadece tasarruf sağlayabilir logspace .

Sorunların azaltılması

Bir sorun, Π olduğunu göstermek için Cı- bir için -difficult verilen sınıf C , usulün iki yol vardır: ya ilişkin bir sorun olduğunu göstermek için C tt azaltır ya da olduğunu göstermek için bir C- tam sorun tt indirgenir. Örneğin; bir bulma problemi, ikinci yöntem ile ispat izin Hamilton devre bir de ilgilidir grafik NP tamamlandı.

Problem NP'de , başka bir deyişle deterministik olmayan bir makinede bir polinom algoritması ile çözülebilir. Örneğin, deterministik olmayan bir şekilde bir devre oluşturmak, sonra bunun Hamiltonian olup olmadığını test etmek yeterlidir.
Yönlendirilmemiş bir grafikte bir Hamilton döngüsü bulma probleminin NP-zor olduğunu biliyoruz. Bununla birlikte, yönsüz bir grafik, her bir kenar için iki karşıt yay oluşturarak yönlendirilmiş bir grafiğe dönüştürülebilir. Bu nedenle, bilinen, NP-tam problemini, yani yönsüz bir grafikte bir Hamilton döngüsünü bulmak, sınıflandırmak istediğimiz probleme, yani yönlendirilmiş bir grafikte bir Hamilton devresi bulmak mümkündür. Bir Hamilton devresinin varlığı sorunu, bu nedenle NP-tamamlanmıştır.

Notlar ve referanslar

(fr) Bu makale kısmen veya tamamen Wikipedia makalesinden alınmıştır İngilizce başlıklı " Karmaşıklık sınıfı " ( yazarların listesini görmek ) .

Michel Serfati ( yön. ), Yöntem: matematik tarihi ve felsefesinde araştırma , PUFC, arş . "Kolokyumlar ve seminerler",2002( ISBN 2848670002 , çevrimiçi okuyun ) , "Turing makinesi ve algoritmik karmaşıklık", s. 206.

Dış bağlantı

Waterloo Üniversitesi'ndeki " Karmaşıklık Hayvanat Bahçesi " , çok sayıda karmaşıklık sınıfını listeleyen bir wiki.