You are here:

- Home
- Computing/Technology
- C/C++
- C++
- Algorithm

Advertisement

If a problem belongs to P class then can it belong to NP class? Answer according to current research in Complexity theory.

The typical question in in computational complexity theory is, "As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change and what are the implications and ramifications of that change?" The theory investigates the scalability of computational problems and algorithms and tries to place practical limits on what computers can accomplish.

Problems are divided into two categories: those for which there exists an algorithm to solve it with polynomial time complexity, and those for which there is no such algorithm. We denote the former class of problems by P. There are problems for which no known algorithm exists that solves it in polynomial time, but there is also no proof that no such algorithm exists. Among these problems that are not known to be in P, there is a subclass of problems known as NP-complete: those for which either all are solvable in polynomial time, or none are. Formally, a problem is NP if there exists an algorithm with polynomial time complexity that can certify a solution.

An important aspect of the theory is to categorize computational problems and algorithms into complexity classes. It is an open (unsolved) question in computational complexity theory whether the complexity class P is the same as the complexity class NP, or is a strict subset as is generally believed. This is perhaps the most important question in computational complexity theory.

see: http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

Opinion is divided, though most experts regard P as not the same as NP and NP-complete problems as having exponential time complexity.

see: http://www.cs.umd.edu/~gasarch/papers/poll.pdf

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 10 | Politeness = 10 |

Comment | No Comment |

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

about 15 years or so**Education/Credentials**

post graduate engineer