18_Algorithm Engineering: Intractable Problems and Complexity Classes

Intractable Problems and Complexity Classes

Intractable Problems

Some problems cannot be solved efficiently by algorithms.
Some problems cannot be solved at all.
Problems can be separated into three broad categories:
1. "Easy": Solved reasonably efficiently. The technical term is P.
2. "Hard": Solved, but only by extremely slow algorithms. The hardest are called NP.
3. "Impossible": Cannot be solved by algorithms. The term is undecidable.

Tractability and Intractability

A problem is called tractable if and only if there is an efficient (i.e., polynomial-time) algorithm that solves it.
A problem is called intractable if and only if there is no efficient algorithm that solves it.
Intractable problems are common.
Techniques for solving them are needed.

P Class Problems

An Algorithm is polynomial if its time complexity is $O(n^k)$ for some $k ≥ 0$
If its time complexity can be upper-bounded by a polynomial, the algorithm is considered a polynomial – $O(1)$ , $O(n)$ , $O(log n)$
The complexity class P is the set of all problems that may be solved by polynomial algorithms – $P = {X | there exists a polynomial algorithm that solves X}$
If an algorithm’s time complexity is $O(n^k log n)$ , the algorithm is polynomial.
- Proof: For sufficiently large n, log n < n
- n * log n < n * n
- n log n < n^2
- $O(n log n) ⊆ O(n^2)$
- Hence, $O(n^k log n) ⊆ O(n^{k+1})$ ; which is a polynomial time complexity of order $(k + 1)$ .

Proving that a problem is in P

For any problem X, if there exists some polynomial algorithm A that solves X, then $X \epsilon P$
- Proof:
  1. Design an algorithm Alg that solves X.
  2. Prove that Alg runs in polynomial time.
  3. Conclude that $X \epsilon P$ .
The following problems are in P:
1. Summation
2. Sequential search
3. Sorting
4. Binary search
5. Minimum spanning tree
6. Single source shortest paths
7. Median finding
8. Set intersection
Circuit satisfaction and traveling salesperson do not have a polynomial-time algorithm, so we cannot say that they are in P.
Implication: Every algorithm analysis we have performed so far, that resulted in a polynomial running time, may be taken as a proof that the problem is in P.

NP Class Problems

A problem is said to belong to NP (nondeterministic polynomial time) class if it is only solvable by a nondeterministic Turing machine.
- A P-problem (whose solution time is bounded by a polynomial) is always NP.
If an algorithm’s time complexity is exponential e.g. $O(2^n)$ , or factorial e.g. $O(n!)$ , the algorithm is not polynomial.
NP is the set of problems for which verifier algorithms have polynomial time and space complexity.
A verifier algorithm is an algorithm that verifies whether a given input is a correct output to a problem.
A problem E is said to be in NP if there exists a verifier algorithm verify_E for the problem such that:
- verify_E takes as input a pair (instance, certificate).
- instance is some instance of the problem E.
- certificate is some piece of data (called certificate).
- verify_E checks whether the certificate is a correct output for the instance of problem E in polynomial time.
- The output of verify_E is “yes” or “no”
  - The output of verify_E is “yes” if the certificate is a correct output for the instance of problem E.
  - The output of verify_E is “no” if the certificate is an incorrect output for the instance of problem E.

Is P a subset of NP?

$X \epsilon P$ implies that $X \epsilon NP$
NP is the set of problems that may be verified, but not necessarily fully solved, in polynomial time.
P is the set of problems that may be completely solved in polynomial time.
Intuitively, if a problem can be solved in polynomial time, we ought to be able to complete the task of verifying the problem in polynomial time too.
Proof:
- By the definition of P, there exists some algorithm solve_X that returns a correct solution to X in polynomial time.
- A verifier algorithm can be created by reduction to solve_x.
$P ⊆ NP$

Decidable vs Undecidable Problems

Problem X is decidable if there exists an algorithm that solves X, or is undecidable if an algorithm that solves X does not exist.
Every problem in P is decidable.
- A decision problem is a problem whose output is Boolean, corresponding to making a yes or no decision.
- When a decision problem is solvable, it is “decidable”; otherwise, it is “undecidable.”
Proving that a problem is decidable is even simpler than proving that a problem is in P.
- By the definition of decidability, all we need to show is that there exists a correct algorithm that solves the problem; analysis of its efficiency is not required.
The circuit satisfaction and traveling salesperson problems are decidable.
Every problem in NP is decidable.

Undecidable Problems

Example of undecidable problems: ill-posed problems
- ill-posed problems: the output definition precludes any algorithm from being provably correct.
  - Example: the meaning of life problem is:
    - input: a string K containing the sum of human knowledge
    - output: a string M containing an English sentence describing the meaning of life
  - It has an input and output which may be represented in finite data structures and precisely-defined size measures.
  - However, there is no way to design a correct algorithm for it since the definition of what constitutes a correct output is subjective.
Another example of undecidable problem: Problem X , such that any algorithm (Solve_X) attempting to solve Problem X does not terminate.

The Halting Problem

input: a procedure proc and input I
output: True if proc halts when run with input I, or False otherwise
“Given an arbitrary Turing Machine T, and an arbitrary tape t as input, decide whether T halts on t.”
First posed by Alan Turing in 1936
He proved that a general algorithm to solve the halting problem for all possible program-input pairs does not exist.
The problem asks for a simple Yes/No: a decision problem which is undecidable.
There is no general algorithm to decide whether the answer is Yes or No.

The Halting Problem Proof

The halting problem is undecidable.
Proof: Argue by contradiction:
- Suppose that there exists an algorithm halts that solves the halting problem. The behavior of halts can be summarized as:
  - halts(proc, I) = True if proc halts on input I
  - halts(proc, I) = False if proc loops forever on input I
- We may create a new process self_halts that uses halts to determine whether a procedure halts when run on itself.
  - def self_halts(proc):
    return halts(proc, proc)
- We may summarize self_halts's behavior as:
  - Self_halts(proc) = True if proc halts on input proc
  - Self_halts(proc) = False if proc loops forever on input proc
- Another opposite procedure contrary that calls self_halts may be introduced
  def contrary(proc): if self_halts(proc): # infinite loop while True: pass else: # halt return

The Halting Problem Contradiction

In general, contrary ’s behavior is What of when contrary is running on itself. By substitution, its behavior becomes:
Both cases are clear contradictions!
So our supposition that halts exists is unsound: an algorithm solving the halting problem does not exist.

The Halting Problem Conclusion

Is it possible to design a machine that accepts machines that do not accept themselves (machines)?
A clear contradiction

Undecidable Problem: More Examples

Another example of an undecidable problem: Entscheidungsproblem (Ger) “decision problem” (David Hilbert in 1928):
- find an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and
  - answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms.
  - find an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.
If the halting problem could be solved, many other problems could be decided:
- Busy Beaver problem
  - Aims at finding a terminating program of a given size that produces the most output possible.
  - A non-computable function: grows faster asymptotically than any computable function.
- The Goldbach Conjecture
  - states that every even integer greater than 4 can be expressed as the sum of two odd primes.
  - another form of the conjecture states that every even integer greater than two can be expressed as the sum of two primes numbers.