On The Duality Feature of P-Class Problems and NP Complete Problems


WenhongTian1,2, 1University of Electronic Science and Technology of China and 2Chongqing Institute of Green and Intelligent Technology, China


In term of computational complexity, P-class (abbreviated as P) problems are polynomial-time solvable by deterministic Turing machine while NP complete (abbreviated as NPC) problems are polynomial-time solvable by nondeterministic Turing machine. P and NPC problems are regularly treated in different classes. Determining whether or not it is possible to solve NPC problems quickly, is one of the principal unsolved problems in computer science today. In this paper, a new perspective is provided: both P problems and NPC problems have the duality feature in terms of computational complexity of asymptotic efficiency of algorithms.


P Problems; NP problems; NP Complete Problems; the P versus NP Problem; The Duality Feature.

Full Text  Volume 8, Number 3