The Question
Is every algorithmic problem whose solution can be efficiently verified is efficiently computable?
Efficient Computation
Runs in time that is a fixed
polynomial of the input size.
P - Polynomial Time
Class of problems with efficient solutions are known as P problems.
NP - Non-Deterministic Polynomial Time
Class of problems whose solution
can be verified efficiently but are difficult to solve especially for large inputs (e.g. Traveling Salesman problem). That is, the problem cannot be solved in deterministic polynomial time (or in other words, efficient computation is not possible).
NP-Complete
Given a set of the very hardest NP problems, find an efficient algorithm for one member in the set and then you can certainly find an efficient algorithm to solve all of the members of set.
NP-Hard
NP-Hard problem is a class of problems that are as the hardest problems in NP.
P = NP
If this is proven to be true, we can find an efficient algorithm to solve any problem that has an efficiently verifiable solution. An efficient solution to any NP-complete problem would imply P=NP and hence an efficient solution to every NP-complete problem.
P ≠ NP
Most computer scientists believe P ≠ NP. That is, not every solution-verifiable problem has an efficient solution.
