Uzay karmaşıklığı - Space complexity

Alan karmaşıklığı , bir bir algoritma ya da bilgisayar programının bir örneğini çözmek için gerekli bellek alanı miktarı hesaplama problem giriş özelliklerinin bir fonksiyonu olarak göstermektedir. Bir algoritmanın tamamen yürütülene kadar ihtiyaç duyduğu bellektir.

Benzer süresi karmaşıklık , uzay karmaşıklığı sık sık asimptotik ifade edilir büyük O notasyonu gibi, vb burada n, giriş etkileyen alan karmaşıklığı bir özelliğidir. ${\görüntüleme stili O(n),}$ ${\displaystyle O(n\log n),}$ ${\ Displaystyle O(n^{\alpha }),}$ ${\görüntüleme stili O(2^{n}),}$

Uzay karmaşıklığı sınıfları

Benzer şekilde zaman karmaşıklığı sınıflarına DTime (f (n)) ve NTIME (f (n)) , karmaşıklık sınıfları dSPACE (f (n)) ve N-Space (f (n)) deterministik tarafından Karar verilebilen dillerin setleri (vardır sırasıyla, deterministik olmayan) Uzay kullanan Turing makineleri . Karmaşıklık sınıfları Pspace ve NPSPACE izin benzer şekilde, herhangi bir polinom olduğu P ve NP . Yani, ${\görüntüleme stili O(f(n))}$${\görüntüleme stili f}$

${\displaystyle {\mathsf {PSPACE}}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$

ve

${\displaystyle {\mathsf {NPSPACE}}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$

sınıflar arasındaki ilişkiler

Uzay hiyerarşi teoremi herkes için, belirtiyor uzay-constructible fonksiyonları olan bir makine tarafından çözülebilir bir sorun vardır bellek alanı, ama asimptotik az olan bir makine tarafından çözülemeyen alanı. ${\görüntüleme stili f(n)}$${\görüntüleme stili f(n)}$${\görüntüleme stili f(n)}$

Karmaşıklık sınıfları arasındaki aşağıdaki sınırlamalar geçerlidir.

${\displaystyle {\mathsf {DTIME}}\left(f\left(n\sağ)\sağ)\subseteq {\mathsf {DSPACE}}\left(f\sol(n\sağ)\sağ)\subseteq { \mathsf {NSPACE}}\left(f\left(n\sağ)\sağ)\subseteq {\mathsf {DTIME}}\left(2^{O\left(f\left(n\sağ)\sağ) }\sağ)}$

Ayrıca, Savitch'in teoremi , eğer , ${\ekran stili f\in \Omega (\log(n))}$

${\displaystyle {\mathsf {NSPACE}}\left(f\sol(n\sağ)\sağ)\subseteq {\mathsf {DSPACE}}\left(\sol(f\sol(n\sağ)\sağ) ^{2}\sağ).}$

Doğrudan bir sonuç olarak, . Bu sonuç şaşırtıcıdır, çünkü determinizmin bir sorunu çözmek için gerekli alanı yalnızca küçük bir miktar azaltabileceğini öne sürer. Buna karşılık, üstel zaman hipotezi , zaman karmaşıklığı için deterministik ve deterministik olmayan karmaşıklık arasında üstel bir boşluk olabileceğini varsayar. ${\ Displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}}$

Immerman-Szelepcsenyi teoremi tekrar için, belirtiyor , tamamlama altında kapalıdır. Bu, deterministik olmayan zaman karmaşıklığı sınıflarının tamamlama altında kapalı olduğuna inanılmadığından, zaman ve uzay karmaşıklığı sınıfları arasındaki başka bir nitel farkı gösterir; örneğin, NP ≠ ko-NP olduğu varsayılır . ${\ekran stili f\in \Omega (\log(n))}$${\görüntüleme stili {\mathsf {NSPACE}}(f(n))}$

LOGSPACE

L veya LOGSPACE, giriş boyutuna göre yalnızca bellek alanını kullanan deterministik bir Turing makinesi tarafından çözülebilen problemler kümesidir . Tüm -bit girdisini indeksleyebilen tek bir sayaç bile alan gerektirir , bu nedenle LOGSPACE algoritmaları yalnızca sabit sayıda sayaç veya benzer bit karmaşıklığına sahip diğer değişkenleri koruyabilir. ${\ Displaystyle O(\log n)}$${\görüntüleme stili n}$${\görüntüleme stili \log n}$

LOGSPACE ve diğer alt-doğrusal uzay karmaşıklığı, bir bilgisayarın RAM'ine sığamayan büyük verileri işlerken kullanışlıdır . Bunlar Akış algoritmaları ile ilgilidir , ancak yalnızca ne kadar belleğin kullanılabileceğini sınırlarken akış algoritmalarının girdinin algoritmaya nasıl beslendiği konusunda daha fazla kısıtlaması vardır. Bu sınıf aynı zamanda , araştırmacıların L = RL olup olmadığı açık problemini düşündükleri , sözde rastgelelik ve derandomizasyon alanında kullanım görmektedir .

Karşılık gelen nondeterministic alan karmaşıklığı sınıftır NL .

Yardımcı uzay karmaşıklığı

Terimi, yardımcı boşluk, giriş tarafından tüketilen daha başka bir boşluğa karşılık gelir. Yardımcı uzay karmaşıklığı, resmi olarak, üzerine yazılamayan, yalnızca okunabilen ayrı bir giriş bandına ve üzerine yazılabilen geleneksel bir çalışma bandına sahip bir Turing makinesi olarak tanımlanabilir . Yardımcı alan karmaşıklığı daha sonra çalışma bandı aracılığıyla tanımlanır (ve analiz edilir). Örneğin, düşünün derinlik ilk arama a dengeli ikili ağacın ile düğümler: onun yardımcı uzay karmaşıklığı olduğunu . ${\görüntüleme stili n}$${\displaystyle \Teta (\log n)}$

Referanslar