Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
1
11
1111
1
1
11
1
1 2 2
2
222
2
2
2
3
3
3
3 4
r
r
T
M,x
A 0
s(|w|)
(k + 2)
A 0
d·s(|w|)
(k + 1) (k + 2)
A z ∈ {1, 2, . . . , r
M
}
∗
d · s(|w|) (k + 2)
z A k
M
w M
A w
M
q
accept
M
w
M n
d · s(n) w A
M w L(A) = L(M) Space
M
(n) ≤ Time
M
(n)
Space
M
(n) ≤ d · s(n) A
Space
M
(n) ≤ d ·s(n) k (k + 1)
O
d·s(|w|)
d·s(n)
(k + 2)
{1, 2, . . . , r}
∗
d · s(n)
Space
A
(n) ≤ d · s(n).
ut
NP ⊆ PSPACE
(k + 2)
A
MMT
∗
s
s(n) ≥ lo g
2
n
NSPACE(s(n)) ⊆
[
c∈IN
0
TIME(c
s(n)
).
M MMT
L(M) = L Space
M
(n) ∈ O(s(n)).
d w
M w
d · s(n).
w ∈ L(M ) M
(q
accept
, w, 0, λ, . . . , λ, 0 )
q
accept
M
¢
12
c
w w
|InConf(|w|)| ≤ c
s(|w|)
.
C
0
, C
1
, . . . , C
|InConf(|w|)|
.
MMT A L(A) = L
w A
A M(w) G(w)
|InConf(|w|)| w
d · s(n) G(w) C
i
C
j
C
i
|−−
M
C
j
C
j
C
i
M
C
k
M w
C
0
M w
M w C
0
C
k
G(w)
A C
k
C
0
A w
L(A) = L (M )
A M (w)
A
|InConf(|w|)| · |InConf(|w|)| ≤ c
d·s(|w|)
· c
d·s(|w|)
≤ c
2d·s(|w|)
m
ij
M(w) m
ij
C
i
C
j
d · s(|w |) · |InConf(|w|)| ≤ c
2d·s(|w|)
.
2d ·s(|w|) C
j
C
i
M A
c
2d·s(|w|)
· (2c
2d·s(|w|)
+ 2d · s(|w|)) ≤ c
12d·s(|w|)
.
C
0
C
k
G(w)
|InConf(|w|)|
O(|InConf(|w|)|
4
)
(c
d·s(|w|)
)
4
= c
4d·s(|w|)
,
Time
A
(n) ∈ O(c
12·d·s(n)
).
ut
NLOG ⊆ P NPSPACE ⊆ EXPTIME.
G(w)
w
∗
s
s(n) ≥ lo g
2
n
NSPACE(s(n)) ⊆ SPACE(s(n)
2
).
PSPACE = NPSPACE.
DLOG ⊆ NLOG ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
DLOG ( PSPACE P ( EXPTIME.
NP
P NP
P = NP P ( NP ?
P
13
G(w)
NP
NP
P NP − P
P P NP
P NP
NP
C M
x C
x ∈ L(M)
M x
x /∈ L(M)
L
x ∈ L(M)
x x /∈ L(M)
x
L = SAT
SAT = {x ∈ (Σ
logic
)
∗
| x }.
Φ ∈ SAT Φ
x ∈ L(M)
M
L(M) = SAT Φ n x
1
, . . . , x
n
M α
1
, . . . , α
n
x
1
, . . . , x
n
14
15
M x
x
1
=0 x
1
=1
x
2
=0x
2
=0
x
2
=1x
2
=1
x
n
=0x
n
=0 x
n
=1 x
n
=1
− 2
n
T
M,Φ
n M Φ(α
1
, . . . , α
n
)
α
1
, . . . , α
n
Φ α
1
, . . . , α
n
Φ α
1
, . . . , α
n
Φ
Φ
α
1
, . . . , α
n
α
1
, . . . , α
n
Φ
M
M
L
HMT
w x ∈ L
w
L ⊆ Σ
∗
p : IN
0
→ IN
0
MMT A
Σ
∗
× (Σ
bool
)
∗
p L
• Time
A
(w, x) ≤ p(|w|) (w, x) ∈ Σ
∗
× (Σ
bool
)
∗
• w ∈ L x ∈ (Σ
bool
)
∗
|x| ≤ p(|w|) (w, x) ∈ L(A) ( A (w, x)).
16
α
1
, . . . , α
n
NP
x w ∈ L
• y /∈ L z ∈ (Σ
bool
)
∗
(y, z) /∈ L(A)
p(n) ∈ O(n
k
) k A
VP = { V (A) | A }.
p A L(A) V (A)
V (A) = {w ∈ Σ
∗
| ∃x ∈ (Σ
bool
)
∗
: |x| ≤ p(|w|), (w, x) ∈ L(A)}.
A L
(w, x) x
w ∈ L w V (A)
x w ∈ L |x| ≤ p(|w|)
A SAT
(w, x) A w
Φ
w
A A
Φ
w
n
x ∈ {0, 1}
∗
|x| < n A
|x| ≥ n A n x
Φ
w
A (w, x)
Φ
w
A
SAT w
x
|x| ≤ |w| (w, x) ∈ L(A),
k G n k ≤ n G
k
CLIQUE = {x#y | x, y ∈ {0, 1}
∗
, x G
x
Number (y) }.
B CLIQUE
(w, z) B
w w = x#y x G
x
y ∈ (Σ
bool
)
∗
B (w, z) B n
G
x
v
1
, . . . , v
n
G
x
B
17
Number(y) ≤ n |z| ≥ dlog
2
ne · Number(y).
B (w, z) B z
dlog
2
ne · Number (y) Number (y) {1, 2, . . . , n } B
Number (y) B
i
1
, i
2
, . . . , i
Number ( y)
Number (y)
B v
i
1
, v
i
2
, . . . , v
i
Number (y)
G
x
B (w, z)
COMPOSITE = { x ∈ (Σ
bool
)
∗
| Number(x) }.
HMT HC
HMT
HMT
VP = NP.
NP ⊆ VP VP ⊆ NP
⊇ NP ⊆ VP L ∈ NP L ⊆ Σ
∗
Σ k ∈ IN
HMT M L = L(M ) Time
M
(n) ∈ O(n
k
)
M
A (x, c) ∈ Σ
∗
×(Σ
bool
)
∗
A c
M A
w M
A c
0 1 A
M x
M A c
A (x, c)
18
A
M x A (x, c)
M x
M A
c
A
L(A) = L (M ).
x ∈ L(M) C
M,x
M
x O(|x|
k
)
c C
M,x
|c| ≤ |C
M,x
| ∈ O(|x|
k
)
A C
M,x
A (x, c)
O(|x|
k
)
x /∈ L(M) M
x A (x, d) d ∈ (Σ
bool
)
∗
L(M) A O(n
k
)
⊆ VP ⊆ NP
L ⊆ Σ
∗
Σ VP
A V (A) = L
HMT M A
x ∈ Σ
∗
M c ∈ (Σ
bool
)
∗
M A (x, c)
M x A (x, c) x
A (x, c)
L(M) = V (A)
Time
M
(x) ≤ 2 · Time
A
(x, c)
x ∈ L(M ) c x
M L ∈ NP
ut
NP L
x ∈ L c
x
x ∈ L
• c
x
x
• c
x
x ∈ L
19
V (A) = L(M)
P
NP
NP
Ω(n)
NP
Ω(n ·log n)
NP
Ω(2
n
)
Ω(n)
NP
P NP
P ( NP
P ( NP
3000 NP
P NP