P和NP指二个问题类。NP存在着二个流行定义(见Sipser的书“Introduction to the Theory of Computation”,Section 7.3[1]): 1,基于验证的定义:NP是“确定型图灵机”在多项式时间内可验证的语言类; 2,基于判定的定义:NP是“非确定型图灵机”在多项式时间内可接受的语言类。 于博文中( http://blog.sciencenet ...
在计算复杂性理论中,NP是用“非确定型图灵机(nondeterministic Turing machine,NDTM)”来定义的,从“语言”的角度,存在着二个流行的定义(见 : Michael Sipser, Introduction to the Theory of Computation, Section 7.3): 1,基于验证的定义:NP是“确定型图灵机”在多项式时间内可验证的语言类; 2,基于判 ...