Изменения

Перейти к: навигация, поиск

NP-полнота задачи BH1N

1 байт добавлено, 18:10, 18 марта 2010
Доказательство принадлежности BH_{1N} классу NP
Если НМТ <tex>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>, удовлетворяющий верификатору. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>.
 
Все условия принадлежности классу <tex>NP</tex> выполнены.
Анонимный участник

Навигация