Komplexitätstheorie kann ganz schön komplex werden:
Mittels der Idee einer Turingmaschine lassen sich
folgende Komplexitätsklassen definieren:
DTIME : deterministisch zeitbeschränkt
NTIME : nichtdeterministisch zeitbeschränkt
NP : nichtdeterministisch polynomiell zeitbeschränkt
P : polynomiell zeitbeschränkt
EXPTIME : exponentiell zeitbeschränkt
P
=
⋃
c
>
0
D
T
I
M
E
(
n
c
+
c
)
{\displaystyle P=\bigcup _{c>0}DTIME(n^{c}+c)}
N
P
=
⋃
c
>
0
N
T
I
M
E
(
n
c
+
c
)
{\displaystyle NP=\bigcup _{c>0}NTIME(n^{c}+c)}
E
=
⋃
c
>
0
D
T
I
M
E
(
2
c
n
)
{\displaystyle E=\bigcup _{c>0}DTIME(2^{cn})}
E
X
P
T
I
M
E
=
⋃
c
>
0
D
T
I
M
E
(
2
n
c
+
c
)
{\displaystyle EXPTIME=\bigcup _{c>0}DTIME(2^{n^{c}}+c)}
DSPACE : deterministisch platzbeschränkt
NSPACE : nichtdeterministisch platzbeschränkt
L/LOGSPACE : logarithmisch platzbeschränkt
NL : nichtdeterministisch logarithmisch platzbeschränkt
LINSPACE : linear platzbeschränkt
PSPACE : polynomiell platzbeschränkt
L
O
G
S
P
A
C
E
=
⋃
c
>
0
D
S
P
A
C
E
(
c
log
c
(
n
)
)
{\displaystyle LOGSPACE=\bigcup _{c>0}DSPACE(c\log _{c}(n))}
N
L
=
⋃
c
>
0
N
S
P
A
C
E
(
c
log
c
(
n
)
)
{\displaystyle NL=\bigcup _{c>0}NSPACE(c\log _{c}(n))}
L
I
N
S
P
A
C
E
=
⋃
c
>
0
D
S
P
A
C
E
(
n
)
{\displaystyle LINSPACE=\bigcup _{c>0}DSPACE(n)}
P
S
P
A
C
E
=
⋃
c
>
0
D
S
P
A
C
E
(
n
c
+
c
)
{\displaystyle PSPACE=\bigcup _{c>0}DSPACE(n^{c}+c)}
D
T
I
M
E
(
t
(
n
)
)
⊆
D
S
P
A
C
E
(
t
(
n
)
)
{\displaystyle DTIME(t(n))\subseteq DSPACE(t(n))}
