Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
n n
2
Z
n
Z
n
dlog
2
ne
c n
K
(01)
2
n
≤ dlog
2
(n + 1)e + c =
l
log
2
log
2
(01)
2
n
/2
m
+ c.
y
1
, y
2
, y
3
, . . .
Σ
bool
• |y
i
| < |y
i+1
| i ∈ IN
• c i ∈ IN
K(y
i
) ≤ dlog
2
log
2
log
2
|y
i
|e + c.
m ∈ IN
w
m
|w
m
| − K (w
m
) > m.
n∈ IN
K (n) = K (Bin(n)).
n = p q
K (n) ≤ K (p) + K (q) + c
c n p q
n ∈ IN w
n
∈ (Σ
bool
)
n
K(w
n
) ≥ |w
n
| = n ,
n ∈ IN n
(Σ
bool
)
n
2
n
x
1
, . . . , x
2
n
i = 1, 2, . . . , 2
n
C Prog(x
i
) ∈ {0, 1}
∗
Prog(x
i
) x
i
K (x
i
) = |C Prog(x
i
)| Prog(x
i
)
x
i
30
31
x
i
i 6= j C Prog(x
i
) C Prog(x
j
)
x
i
x
j
2
n
C Prog(x
1
), C Prog(x
2
), . . . , C Prog(x
2
n
)
x
1
, x
2
, . . . , x
2
n
n
2
n
n
(Σ
bool
)
∗
i Σ
bool
2
i
Σ
bool
n − 1
n−1
X
i=1
2
i
= 2
n
− 2 < 2
n
.
C Prog(x
1
), . . . , C Prog(x
2
n
)
n C Prog(x
j
)
|C Prog(x
j
)| ≥ n.
|C Prog(x
j
)| = K (x
j
),
x
j
ut
i, n ∈ IN i < n 2
n
− 2
n−i
x (Σ
bool
)
n
K(x) ≥ n − i.
m
K (m) ≥ dlog
2
me − 1.
x Σ
bool
A K
A
(x) x
A
A x
A B
c
A,B
A B
|K
A
(x) − K
B
(x)| ≤ c
A,B
x ∈ (Σ
bool
)
∗
U
A→B
A B U
A→B
B
P
A
A
P
B
B U
A→B
P
B
x P
A
U
A→B
P
A
A U
A→B
P
A
U
A→B
P
A
B
P
A
c
A→B
U
A→B
P
x
A
x U
A→B
P
x
x U
A→B
B
K
B
(x) ≤ K
A
(x) + c
A→B
.
U
B→A
B
A c
B→A
K
A
(x) ≤ K
B
(x) + c
B→A
x ∈ (Σ
bool
)
∗
c
A,B
c
A→B
c
B→A
|K
A
(x) − K
B
(x)| ≤ c
A,B
.
ut
(Σ
bool
)
n
0
n
x ∈ (Σ
bool
)
∗
K (x) ≥ |x|.
n
K(n) = K(Bin(n)) ≥ dlog
2
(n + 1)e − 1.
1 dlog
2
(n+1)e
1
(Σ
bool
, L)
L
L x ∈ L
log
2
|x|
L Σ
bool
n z
n
n
A
L
(Σ
bool
, L)
c n
K (z
n
) ≤ dlog
2
(n + 1)e + c,
n
32
n C
n
z
n
C
n
A
L
C
n
i = 0
x := λ
i <n
h A
L
(x) x A
L
i
A
L
(x) = 1
i := i + 1
z := x
x := x
(z)
C
n
(Σ
bool
)
∗
x C
n
x ∈ L A
L
C
n
A
L
C
n
n z
n
L
C
n
n c C
n
n n ∈ IN C
n
c + dlog
2
(n + 1)e.
C
n
z
n
K (z
n
)
ut
C
n
c i z
C
n
C
n
C
n
C
n
n C
n
n
p
L ⊆ (Σ
bool
)
∗
|L ∩
(Σ
bool
)
n
| ≤ p(n) n m z
m
m L
K (z
m
) m
n Prim (n)
n
1, , , 4, , 6, , 8 , 9, 10 , , 12, , 14, 1 5, 16, , 18, , 20, 21, 22, , . . .
lim
n→∞
Prim (n)
n/ ln n
= 1.
ut
n/ ln n n
Prim (n)
n Prim (n)
Prim (n)
(n/ ln n)
10
3
168 ∼ 1.161
10
6
78 498 ∼ 1.084
10
9
50 847 478 ∼ 1.053
Prim (n) n/ ln n
n ≥ 67
ln n −
3
2
<
n
Prim (n)
< ln n −
1
2
.
i ∈ IN p
i
i
lim
n→∞
p
n
n ln n
= 1.
Prim (n) / n 1/ ln n
n
33
Prim (n) /(n/ ln n) 1
n/ ln n
S = n
1
, n
2
, n
3
, . . .
K (n
i
) ≥ dlog
2
n
i
e/2 i ∈ IN
q
i
n
i
Q = {q
i
| i ∈ IN}
Q = {q
i
| i ∈ IN}
p
m
p
m
n
i
i ∈ IN
S
n
i
= p
r
i,1
1
·p
r
i,2
2
· ··· · p
r
i,m
m
r
i,1
, r
i,2
, . . . , r
i,m
∈ IN
0
p
1
, p
2
, . . . , p
m
S r
i,1
, r
i,2
, . . . , r
i,m
n
i
A
i
r
i,1
, . . . , r
i,m
n
i
c A
i
r
i,1
, . . . , r
i,m
A
i
K (n
i
) i ∈ IN
34
K (n
i
) ≤ c + dlog
2
(r
i,1
+ 1)e + dlog
2
(r
i,2
+ 1)e + ··· + dlog
2
(r
i,m
+ 1)e.
r
i,j
≤ log
2
n
i
j ∈ {1, 2, . . . , m} i ∈ IN
K (n
i
) ≤ c + m · dlog
2
(log
2
n
i
+ 1)e.
m c i
dlog
2
n
i
e/2 ≤ c + m · dlog
2
(log
2
n
i
+ 1)e
i
K (n
i
) ≥ dlog
2
n
i
e/2
n ut
n
1
, n
2
, n
3
, . . .
K (n
i
) ≥ dlog
2
n
i
e/2
t n
{2
t
, 2
t
+ 1, . . . , 2
t+1
− 1}
K (n) ≥ dlog
2
ne/2 ?
Prim (n)
∗
k ∈ IN
Prim (k) ≥
k
64 log
2
k · (log
2
log
2
k)
2
.
p
j
j
n ≥ 2 p
m
n
n p
m
, n/p
m
p
m
n/p
m
(m, n/p
m
)
m p
m
m
(m, n/p
m
)
Σ
bool
Bin(m)
Bin(n/p
m
)
Bin(m)Bin(n/p
m
)
Bin(m) Bin(n/p
m
)
Bin(m)
Bin(m) = a
1
a
2
a
3
. . . a
dlog
2
(m+1)e
a
i
∈ Σ
bool
i = 1, 2, . . . , dlog
2
(m + 1)e
Bin (m) = a
1
0a
2
0a
3
0 . . . a
dlog
2
(m+1)e−1
0a
dlog
2
(m+1)e
1.
Bin (m)Bin(n/p
m
) (m, n/p
m
)
n
Bin (m) m 1
Bin (m)Bin(n/p
m
)
2 · dlo g
2
(m + 1)e + dlog
2
n
p
m
+ 1
e.
(m, n/p
m
)
Bin (dlog
2
(m + 1)e)Bin(m)Bin(n/p
m
).
Bin (dlog
2
(m + 1)e) 1
Bin (dlog
2
(m + 1)e) dlog
2
(m + 1)e
Bin(m) (m, n/p
m
)
2dlog
2
dlog
2
(m + 1)ee + dlog
2
(m + 1)e + dlog
2
n
p
m
+ 1
e.
(m, n/p
m
)
Word (m, n/ p
m
) =
Bin (dlog
2
dlog
2
(m + 1)ee)Bin(dlog
2
(m + 1)e)Bin(m)Bin(n/p
m
).
|Word (m, n/p
m
)| = 2 · dlog
2
dlog
2
dlog
2
(m + 1)eee
+dlog
2
dlog
2
(m + 1)ee
+dlog
2
(m + 1)e + dlog
2
n
p
m
+ 1
e.
Word (m, n/ p
m
) Bin(n)
n
i ∈ IN n
S
i
= {2
i
, 2
i
+ 1, . . . , 2
i+1
− 1},
|Word (m, n/p
m
)| ≥ dlog
2
(n + 1)e − 1.
n S
i
K (n) ≥ dlog
2
(n + 1)e − 2.
i
n
i
∈ S
i
2
i
≤ n
i
≤ 2
i+1
− 1
|Word (m, n
i
/p
m
)| ≥ dlog
2
(n
i
+ 1)e − 1
K (n) ≥ dlog
2
(n
i
+ 1)e − 2.
n
|Word (m, n/p
m
)| ≥ dlog
2
(n + 1)e − 1
K (n) ≥ dlog
2
(n + 1)e − 2.
dlog
2
(n + 1)e − 1 ≤ 2dlog
2
dlog
2
dlog
2
(m + 1)eee
+dlog
2
dlog
2
(m + 1)ee + dlog
2
(m + 1)e + dlog
2
n
p
m
+ 1
e.
log
2
(n/p
m
) = log
2
n − log
2
p
m
log
2
p
m
≤ 2 · dlog
2
log
2
log
2
(m + 1)e + dlog
2
log
2
(m + 1)e + dlog
2
(m + 1)e + 2
≤ 2 · log
2
log
2
log
2
m + log
2
log
2
m + log
2
m + 6 .
p
m
≤ 64 · m · log
2
m · (log
2
log
2
m)
2
.
n
1
, n
2
, n
3
, . . .
p
m
m
64 · m · log
2
m · (log
2
log
2
m)
2
m
m 64 ·m ·log
2
m ·(log
2
log
2
m)
2
m
Prim
64 · m · log
2
m · (log
2
log
2
m)
2
≥ m.
k = 64 ·m · log
2
m · (log
2
log
2
m)
2
k ≥ m
Prim (k) ≥ m =
k
64 · log
2
m · (log
2
log
2
m)
2
≥
k
64 · log
2
k · (log
2
log
2
k)
2
.
ut