You are here:

C++/Algorithm

Advertisement


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

Answer
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

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

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.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.