Intractability (1)

Problems that can be solved in theory (e.g., given infinite time), but which in practice take too long for their solutions to be useful, are known as intractable problems.

Foundations for the theory of
NP-completeness
NP: Non-deterministic Polynomial-time

1. Polynomial Time Reducibility
If there exist a polynomial time reduction from one problem to another, existence of any polynomial time algorithm for the second problem implies existence of a corresponding polynomial time algorithm for the first problem.

Given a function f(n) is O(g(n)) i.e. there exists some constant c such that |f(n)|<=c|g(n)| for all n>=0.
A polynomial time algorithm is then defined to be the one whose time complexity function is O(p(n)) for some polynomial function p, where n is the input length.

2. Most of the apparently intractable problems encountered belong to the class NP of decision ("yes-no") problems that can be solved in polynomial time by a nondeterministic computer.

3. There is one particular problem in NP known as the "satisfiability" problem which every other problem in NP can be polynomially reduced to.
This implies:
Showing how solvable is the satisfiability problem means how solvable is every problem in NP as well.
Therefore, the satisfiability problem is the "hardest" problem in NP.


All the provably intractable problems known to date are either undecidable or "non-deterministically" intractable.