сокращение отображения за полиномиальное время для NP

Question

Я уже доказал переходное свойство для сокращений отображения за полиномиальное время, а именно:

, если A сводится к B, а B сводится к C, то A сводится к C.

Итак, зная, что B - это NP, а A - отображение за полиномиальное время, сводимое к B, как мне доказать, что A также является NP?

Answer 1

B находится в NP, поэтому есть некоторая машина Тьюринга, назовем ее M (B), которая решает B за полиномиальное время. Кроме того, поскольку A сводится к B за полиномиальное время, существуют TM, давайте назовем их M (R) и M (R '), которые преобразуют входные экземпляры A во входные экземпляры B, а выходы B - в выходы A , оба в полиномиальное время. Рассмотрим TM, построенный следующим образом:

1. Выполнить M (R) на входной ленте и затем сбросить головку ленты
2. Выполнить M (B) на входной ленте и затем сбросить головку ленты
3. Выполнить M (R ') на входной ленте и затем сбросить головку ленты

Каждый из этих шагов занимает полиномиальное время, поэтому весь процесс занимает полиномиальное время. Поскольку недетерминированные машины Тьюринга закрываются при конкатенации (путем замены halt_accept в LHS начальным состоянием RHS), вычисление может быть выполнено одной недетерминированной машиной Тьюринга, объединяющей эти этапы. Таким образом, A может быть определено недетерминированной машиной Тьюринга за полиномиальное время - критерий включения в NP.