Nearly all of the algorithms introduced so far run in polynomial time (for instance, on inputs of size n, their worst-case running time is O(nk) for constant k). However, there are problems that simply cannot be solved or for which a polynomial-time algorithm hasn't been found yet.
An example of a problem that cannot be solved is the halting problem. The halting problem is the problem of determining, from the description of a computer program and an input, whether the program will finish running or continue to run forever. Alan Turing proved that a general algorithm to solve the halting problem for all pairs of (program, input) cannot exist.
It is common to call problems solvable by polynomial-time algorithms (for instance, those whose worst-case running time is O(nk) for constant k) as "tractable", or "easy", and problems that require a super-polynomial-time algorithm (for instance, those whose running time is not bounded above by any polynomial) as "intractable", or "hard".
There is a class of problems, called NP-Complete (NPC) problems, and no one has yet found a polynomial-time algorithm to solve them. However, no one has yet been able to prove that no polynomial-time algorithm can exist for any of them.
There is another class of problems, called NP problems, whose solutions are verifiable in polynomial time. This means that, given a problem, and a possible solution to it, one can verify if the solution is correct in polynomial time.
All problems in P are also in NP. NPC consists of problems that belong to the NP class and to the NP-hard class. A problem is NP-hard if an algorithm for solving it can be translated into one for solving a NP problem.
One of the deepest open research problems in theoretical computer science is whether P is really different from NP (for instance, P != NP).
Examples of NPC problems are as follows:
- Finding the longest path in the graph
- Finding a path in a graph that visits all vertices exactly once (known as a Hamiltonian path)
A common example of an NP-hard problem is finding the shortest path in a graph that visits all vertices exactly once and returns to the starting point. The problem consists of finding the Hamiltonian cycle of the smallest weight, and is often described as the traveling salesman problem as it models the problem of a salesman that needs to visit all cities and return to his hometown.