Составители:
Рубрика:
compl(G)=2(2T+1)+C
2
+ 1 + 2(2T+1)= 4(2T+1)+C
2
+ 1.
2T+1 2T+1
Из приведенных выражений видно, что можно построить к.н.ф.
Φ=B&C&D&E&F&G, которая утверждает, что существует такое
допустимое y, что машина, начав работу в конфигурации q
1
z*y,
перейдет в заключительную конфигурацию q
1.
0
Если задача z∈Z
П
имеет положительный ответ, то для
некоторого допустимого y выполняется R(z,y)=1. В этом случае,
начав работу в конфигурации q
1
z*y, получим заключительную
конфигурацию q
i j
1, и, если назначить переменным u , v
0 s,t t
и w
s,t
значения, соответствующие y, то получим набор, на котором Φ=1.
Обратно, если существует набор, обращающий Φ в 1, то значения
переменных u
i
s,0
(0≤i≤k-1, n+2≤s≤T) определяют слово y такое, что
машина переводит q
z*y в q
1 0
1 и, следовательно, задача z имеет
положительный ответ. Тем самым задача Z
П
сведена к задаче
выполнимости к.н.ф.
Сложность формулы Φ=B&C&D&E&F&G равна сумме
сложностей ее компонентов, для которых выше были приведены
полиномиальные выражения. Поэтому сложность Φ ограничена
полиномом от n=l(z), причем при записи этой формулы в некотором
алфавите ее длина возрастет примерно в log(compl(Φ)) раз и
останется полиномиально ограниченной. Рассмотрение формулы Φ
показывает, что от индивидуальной задачи z зависит лишь
сомножитель &
z(m)
u в выражении для E
1≤m≤n m,0 1
и величины n=l(z) и
T=P(n). В остальном формула Φ определяется машиной M и,
следовательно, массовой задачей Z
П
. Таким образом, сведение
осуществлено с полиномиальной сложностью. Теорема доказана.
178
Страницы
- « первая
- ‹ предыдущая
- …
- 92
- 93
- 94
- 95
- 96
- …
- следующая ›
- последняя »
