Open topic: 在阅读资料JH中，作者是用 来定义NP的。请你说说两种定义方法是一致的吗？为什么？

Presentation on theme: "Open topic: 在阅读资料JH中，作者是用 来定义NP的。请你说说两种定义方法是一致的吗？为什么？"— Presentation transcript:

1 Open topic: 在阅读资料JH中，作者是用 来定义NP的。请你说说两种定义方法是一致的吗？为什么？

2 两种NP的定义： TC: JH:

3 图灵机 图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵 （1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算 的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。 所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了 一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移 去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都 要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表， 根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

4 Deterministic and Non-deterministic Turing Machine
In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation. By contrast, a non-deterministic Turing machine (NTM) may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set. A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left, right or neither) in which the head should move, and the subsequent state of the finite control.

5 Deterministic and Non-deterministic Turing Machine
A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left, right or neither) in which the head should move, and the subsequent state of the finite control. A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left, right or neither) in which the head should move, and the subsequent state of the finite control.

6 Deterministic and Non-deterministic Turing Machine
A non-deterministic Turing machine (NTM) differs in that the state and tape symbol no longer uniquely specify these things; rather, many different actions may apply for the same combination of state and symbol. For example, an X on the tape in state 3 might allow the NTM to write a Y, move right, and switch to state 5, or to write an X, move left, and stay in state 3.

7 非确定性，可以直观地理解成“并行”。非确定性图灵机可以同时检查所有的计算分支（当然，计算分支数要是常数）。
可以想象一个计算树，非确定性图灵机在每个节点上，要转移状态的时候，可以同时检查后面的所有分支

8 两种NP的定义： TC: JH: 存在确定性的Verifier(多项式时间内验证)=>非确定性图灵机可以多项式时间验证

9 Equivalence of NP definitions
To show this, first suppose we have a deterministic verifier. A nondeterministic machine can simply nondeterministically run the verifier on all possible proof strings (this requires only polynomially many steps because it can nondeterministically choose the next character in the proof string in each step, and the length of the proof string must be polynomially bounded). If any proof is valid, some path will accept; if no proof is valid, the string is not in the language and it will reject.

10 Equivalence of NP definitions
Conversely, suppose we have a nondeterministic TM called A accepting a given language L. At each of its polynomially many steps, the machine's computation tree branches in at most a finite number of directions. There must be at least one accepting path, and the string describing this path is the proof supplied to the verifier. The verifier can then deterministically simulate A, following only the accepting path, and verifying that it accepts at the end. If A rejects the input, there is no accepting path, and the verifier will always reject.