Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
• n
j
j ∈ IN
• c · n c ∈ IN
• 2
n
• c
n
c ∈ IN −{1}
s(n) t(n)
t(n)·s(n)
s
MMT M L(M ) = L
s(n)
MMT A L s(|x|)
L L
{
s : IN
0
→ IN
0
M MMT Space
M
(x) ≤ s(|x|) x ∈ L(M )
MMT A L(A) = L(M)
Space
A
(n) ≤ s(n)
Space
A
(y) ≤ s(|y|) y M
M k MT k ∈ IN
Space
M
(x) ≤ s(|x|) x ∈ L(M ) B MT
s (k + 1) MT A L(A) = L(M)
Space
A
(n) ≤ s(n) x
A x 0
|x|
(k + 1)
B 0
|x|
(k + 1) 0
s(|x|)
A # /∈ Γ
M
s(|x|)
A M x
k M
A A
q
reject
A
M x A x
M x
Space
A
(z) ≤ s(|z|) z L(A) = L(M)
x ∈ L(M ) Space
M
(x) ≤ s(|x|) A
M x q
accept
x ∈ L(A)
9
MMT M L = L(M) Space
M
(x) ≤ s(|x|)
x ∈ Σ
∗
y /∈ L(M)
Space
M
(y) ≤ s(|y|) A M y
y
Space
M
(y) > s(|y|) A M
s(|y|) A
q
reject
y /∈ L(A) ut
t : IN
0
→ IN
0
M MMT x ∈ L(M)
Time
M
(x) ≤ t(|x|) MMT A L(A) = L(M)
Time
A
(n) ∈ O (t(n)).
s t SPACE(s) TIME(t)
Space
M
T ime
M
Space
M
(n) = max{Space
M
(x) | x ∈ Σ
n
}
Time
M
(n) = max{T ime
M
(x) | x ∈ Σ
n
}
Space
M
(n) = max{Space
M
(x) | x ∈ L(M ) |x| = n}
Time
M
(n) = max{Time
M
(x) | x ∈ L(M ) |x| = n}.
s s(n) ≥
log
2
n
SPACE(s(n)) ⊆
[
c∈IN
0
TIME(c
s(n)
).
L ∈ SPACE(s(n))
MT M = (Q, Σ, Γ, δ, q
0
, q
accept
, q
reject
) L = L(M) Space
M
(n) ≤
s(n)
C = (q, w, i, x, j) M
C
In(C) = (q, i, x, j).
In(C) C
w
w
n ∈ N InConf(n)
M n
M w
|InConf(|w|)| M w
|InConf(|w|)|
MMT A M
O(|InConf(|w |)).
|InConf(n)|
(q, i, x, j) ∈ InCo nf(n)
0 ≤ i ≤ n + 1 |x| ≤ Space
M
(n) ≤ s(n) 0 ≤ j ≤
Space
M
(n) ≤ s(n)
|InConf
M
(n)| ≤ |Q| · (n + 2) · |Γ |
Space
M
(n)
·Space
M
(n)
≤ (max{2, |Q|, |Γ |})
4·s(n)
≤ c
s(n)
c = (max{2, |Q|, |Γ |})
4
w n n ≥ |InConf
M
(n)|
D = C
1
, C
2
, C
3
, . . . M w
C
i
C
j
In(C
i
)
In(C
j
)
C
i
C
j
M
D = C
1
, . . . , C
i−1
, C
i
, C
i+1
, . . . , C
j−1
, C
i
, C
i+1
, . . . , C
j−1
, C
i
. . .
C
i
, C
i+1
, . . . , C
j
M w
|InConf
M
(|w|)|
n |InConf
M
(n)|
MT A L(A) = L(M)
Time
A
(n) ∈ O (k
s(n)
) k w
A
A s 0
s(|w|)
{ MT s s(|w|)
d Time
B
(n) ≤ d
s(n)
A 0
s(|n|)
d
s(n)
}
A 0
c
s(|w|)
c
s(|w|)
A
A M w
A 0
0
A q
reject
M w c
s(|w|)
A w
M
A
O(d
s(|w|)
) O(c
s(|w|)
) A
O(c
s(|w|)
)
Time
A
(n) ∈ O((max{c, d})
s(|w|)
).
x ∈ L(M ) M x c
s(|w|)
A x
x /∈ L(M) A x
M ut
DLOG ⊆ P PSPACE ⊆ EXPTIME
DLOG ⊆ P ⊆ PSPACE ⊆ EXPTIME.
∗
s
1
s
2
IN
0
IN
0
• s
2
(n) ≥ lo g
2
n
• s
2
• s
1
(n) = o(s
2
(n))
SPACE(s
1
) ( SPACE(s
2
).
∗
t
1
t
2
IN
0
IN
0
• t
2
• t
1
(n) · log
2
(t
1
(n)) = o(t
2
(n))
TIME(t
1
) ( TIME(t
2
).
TIME(2
n
)
2
n
10n, 2n
2
, n
3
, 2
n
n!
n
f(n)
n
2n
2
n
3
2
n
n! ≈ 3.6 · 10
6
10 50 100 300
10
6
A Time
A
(n) = n
3
n = 300 3
Time
A
(n) = 2
n
A 50 3
n = 100 3 · 10
15
2
n
n!
21
n
3
2
n
t
• n
3
3
√
2 t
1/3
3
√
2 · t
1/3
3
√
2
• 2
n
1
O(n
c
)
c TIME(2
n
)
TIME(n
3
)
A
Time
A
(n) ∈ O (n
c
) c
P
•
n
1000
n
1000
n
1000
> 2
n
n
•
MMT
TIME(n
6
)
P
A B
p A ∈ A
B ∈ B A
Time
B
(n) ∈ O (p(Time
A
(n))).
10
A B
A B
p(n) = n
p(n) ∈ O (n
3
)
U
U
L
L
MMT A Time
A
(n) ≥ n
MT B
Time
B
(n) ∈ O ((Time
A
(n))
2
).
M w
M
w M w
M
x ∈ L(M) ⊆
Σ
∗
M x Time
M
(x)
M x
M Time
M
: IN
0
→ IN
0
Time
M
(n) = max {Time
M
(x) | x ∈ L(M ) ∩ Σ
n
}.
11
C = C
1
, C
2
, . . . , C
m
M
x Space
M
(C
i
) C
i
Space
M
(C) = max{Space
M
(C
i
) | i = 1, 2, . . . , m} .
M x
Space
M
(x) = min{Space
M
(C) | C
M x}.
M Space
M
: IN
0
→ IN
0
Space
M
(n) = max {Space
M
(x) | x ∈ L(M ) ∩ Σ
n
}.
f, g : IN
0
→ IR
+
NTIME(f) = {L(M ) | M MMT
T ime
M
(n) ∈ O (f(n))},
NSPACE(g) = {L(M) | M
MMT
Space
M
(n) ∈ O (g(n))},
NLOG = NSPACE(log
2
n),
NP =
[
c∈IN
0
NTIME(n
c
),
NPSPACE =
[
c∈IN
0
NSPACE(n
c
).
t s
NTIME(t) ⊆ NSPACE(t)
NSPACE(s) ⊆ NTIME(c
s(n)
) c
L ∈ NTIME(t) MMT
M d n
L(M) = L Time
M
(n) ≤ d ·t(n).
x ∈ L(M)
C
x
M x d · t(|x|)
M d · t(n) d · t(n)
Space
M
(C
x
) ≤ d · t(|x|).
Space
M
(n) ≤ d · t(n)
n L ∈ NSPACE(t)
L ∈ NSPACE(s) s
MMT A d
x ∈ L(A) = L
L = L(M ) Space
A
(x) ≤ d ·s(|x|).
x ∈ L(A)
C
x
Space
A
(C
x
) ≤ d · s(|x|).
C
x
A x
x ∈ L(A) k C
x
|InConf
A
(|x|)| ≤ k
d·s(|x|)
.
C
x
|InConf
A
(|x|)|
i, j ∈ IN, i 6= j
C
x
= C
1
, C
2
, . . . , C
i−1
, C
i
, C
i+1
, . . . , C
j
, C
j+1
, . . . , C
m
C
i
C
j
C
0
x
= C
1
, C
2
, . . . , C
i−1
, C
i
, C
j+1
, . . . , C
m
A x
C
0
x
C
x
C
x
A
x Space
A
(C
x
) ≤ d ·s(|x|)
x ∈ L(A)
A
k
d·s(|x|)
= c
s(|x|)
c = k
d
k d
Time
A
(n) ∈ O (c
s(n)
),
L ∈ NTIME(c
s(n)
) ut
M MMT
Time
M
(n) ≤ t(n) t
MMT A
• L(A) = L (M )
• d w ∈ Σ
∗
A w d · t(|w|)
t : IN
0
→ IR
+
s : IN
0
→ IN
0
s(n) ≥ lo g
2
n
TIME(t) ⊆ NTIME(t)
SPACE(t) ⊆ NSPACE(t)
NTIME(s(n)) ⊆ SPACE(s(n)) ⊆
S
c∈IN
0
TIME(c
s(n)
)
MMT
MMT
SPACE(s(n)) ⊆
[
c∈IN
0
TIME(c
s(n)
)
NTIME(s(n)) ⊆ SPACE(s(n)).
L ∈ NTIME(s(n)) k MT
M = (Q, Σ, Γ, δ
M
, q
0
, q
accept
, q
reject
)
L = L(M ) Time
M
(n) ∈ O (s(n)).
r = r
M
= max{|δ
M
(U)| | U = (q, a, b
1
, . . . , b
k
) ∈ Q ×(Σ ∪ {¢, $}) × Γ
k
}
M
T
M,x
M x ∈ Σ
∗
δ
M
U 1, 2, . . . , r T
M,x
M x l
z = z
1
z
2
. . . z
l
∈ {1, 2, . . . , r}
∗
.
M x z
• M x
z = r322 T
M,x
r
3 2
2
•
z = 24 . . .
4
d
M w d · s(|w|)
M w d·s(|w|)
(k + 2) A
M |InConf
M
(n)|
w ∈ Σ
∗
A