Составители:
Рубрика:
B=& B
0≤t≤T
B
t
,
где
B w (
⎯
w \/
⎯
wB
t
= (\/ )(&
-T≤s≤T s,t -T≤s<q≤T s,t q,t
)) – условие того, что на
такте t обозревается ровно одна ячейка ленты.
В выражении для B
B
t
дизъюнкция \/
-T≤s≤T
w
s,t
означает, что на
такте t обозревается некоторая ячейка. Отметим, что сложность
этой формулы равна 2T+1. Формула &
-T≤s<q≤T
(
⎯
w \/
⎯
w
s,t q,t
) - это
условие того, что на такте t обозревается не более одной ячейки.
Действительно, если хотя бы две переменные w
и w
s,t q,t
одновременно
равны 1, эта формула принимает значение 0. Сложность
рассматриваемой формулы равна числу всевозможных пар w
и w
s,t q,t
,
т.е. числу сочетаний C
2
2T+1
=T(2T+1). Поскольку формула для B
содержит T+1 подформул вида B
t
B , сложность формулы B оценивается
полиномом
compl(B)=(T+1)(2T+1+ T(2T+1))=2T
3
+5T
2
+4T+1.
Высказывание C обозначает, что на каждом такте t (0≤t≤T) в
любой ячейке s (-T≤s≤T) находится ровно 1 символ:
C=&
C & ,
0≤t≤T -T≤s≤T s,t
где
i i m
C u (
⎯
u \/
⎯
u = (\/ )(&
s,t 0≤i≤k-1 s,t 0≤i<m≤k-1 s,t q,t
)) – высказывание о
том, что на такте t в ячейке s находится ровно 1 символ.
Формула для C строится аналогично формуле A и имеет
полиномиальную сложность:
compl(C)=(T+1)(2T+1)(k+C
2
k
)=k(k+1)(2T
2
+3T+1)/2.
Высказывание D обозначает, что на каждом такте t (0≤t≤T) машина
находится ровно в одном состоянии:
D=&
D
0≤t≤T t
,
где
j j m
D v (
⎯
v
t
= (\/
0≤j≤r-1 t
)(&
0≤j<m≤r-1 t
\/
⎯
v
t
)) – обозначает, что на
такте t машина находится ровно в одном состоянии.
Формула для D строится аналогично формулам для A, B и имеет
полиномиальную сложность:
175
Страницы
- « первая
- ‹ предыдущая
- …
- 89
- 90
- 91
- 92
- 93
- …
- следующая ›
- последняя »
