Wednesday, August 26, 2020

ON THE DUALITY FEATURE OF P-CLASS PROBLEMS AND NP COMPLETE PROBLEMS

 Author :  WenhongTian

Affiliation :  1University of Electronic Science and Technology of China, Chengdu

Country :  China

Category :  Computer Science & Information Technology

Volume, Issue, Month, Year :  8, 3, February, 2018

Abstract :

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.

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

For More Detailshttps://airccj.org/CSCP/vol8/csit88303.pdf

No comments:

Post a Comment