DTIME

Olarak karmaşıklık teorisi , DTime (ya da SAAT ) bir ailesini tanımlar karmaşıklık sınıfları da karakterize zaman karmaşıklığı bir ilgili deterministik Turing makinası .

Daha kesin olarak, bir boyut girdisi için deterministik bir Turing makinesi tarafından zamanla çözülebilen karar problemleri sınıfıdır . DTbenME(f(değil)){\ displaystyle {\ mathsf {DTIME}} (f (n))}değil{\ displaystyle n}Ö(f(değil)){\ displaystyle {\ mathcal {O}} (f (n))}

Tanımlar

Girdinin boyutuna göre polinom zamanında deterministik bir Turing makinesi tarafından karar verilebilen karar problemlerinin P sınıfı şu şekilde tanımlanabilir:

P=⋃k∈DEĞİLDTbenME(değilk){\ displaystyle {\ mathsf {P}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} (n ^ {k})}

Benzer şekilde, üstel zamandaki karar verilebilir karar problemlerinin EXPTIME sınıfı şu şekilde tanımlanır:

EXPTbenME=⋃k∈DEĞİLDTbenME(2değilk){\ displaystyle {\ mathsf {EXPTIME}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} \ sol (2 ^ {n ^ {k}} \ sağ)}

Zaman hiyerarşisi

Gayri resmi olarak, deterministik zaman hiyerarşi teoremi , daha fazla zamana sahip olmanın daha fazla soruna karar verilmesine izin verdiğini gösterir. Tüm fonksiyonlar için Daha doğrusu, ve öyle ki ve bir süre içinde constructible aşağıdaki sıkı içerme doğrulandı: f{\ displaystyle f}g{\ displaystyle g}fgünlük⁡f=Ö(g){\ displaystyle f \ log f = o (g)}g{\ displaystyle g}

DTbenME(f(değil))⊊DTbenME(g(değil)){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subsetneq {\ mathsf {DTIME}} (g (n))}

Diğer sınıflarla bağlantılar

DTIME sınıfları, uzaydaki herhangi bir yapılandırılabilir işlev için aşağıdaki eklemelerle DSPACE ve NSPACE uzay karmaşıklık sınıflarına bağlanır : f{\ displaystyle f}

DTbenME(f(değil))⊆DEĞİLTbenME(f(değil))⊆DSPATVSE(f(değil))⊆DEĞİLSPATVSE(f(değil))⊆DTbenME(2Ö(f(değil))){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subseteq {\ mathsf {NTIME}} (f (n)) \ subseteq {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DTIME}} \ left (2 ^ {{\ mathcal {O}} (f (n))} \ right)}

Kaynakça

• (tr) Sanjeev Arora ve Boaz Barak , Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım , Cambridge University Press ,20 Nisan 2009, 579  s. ( ISBN  978-0-521-42426-4 , çevrimiçi okuyun ). 
• Sylvain Perifel, Algoritmik karmaşıklık , Éditions Ellipses ,22 Nisan 2014, 432  s. ( ISBN  978-2-729-88692-9 , çevrimiçi okuyun ).