Computational Complexity

Instead of analysing the complexity of a given algorithm, e.g. Bubble Sorts complexity of O(n²) or Heap Sort's complexity of O(n log n), it would be better to know the complexity of a specific problem, like the complexity of the most efficient algorithm to solve a certain class of problems.

Class P Problems

Tractable problems, that are solvable by an algorithm within a worst-time complextiy of O(nc). These algorithms are called polynomial-time algorithms. Problems in class P are e.g. sortin an ordered list, because algorithms to sovle this are in O(n²). Bubble, Insertion, Merge and Quick Sort are all polynomial-time algorithms.

While more efficient algorithms are found for a problem, the upper bound closes in on the lower bound, where proofs reside that a particular problem requires at least a certain time complexity.

Upper Bound
An algorithm's worst case O(n³) for problem p
An algorithm'#s worst case O(n²) for problem p
\/ \/ \/

Computational Problem with Complexity O(?)

/\ /\ /\
Lower Bound
A Proof that p requires at least O(n log n)
A Proof that p requires at least O(n)

Intractable problems do need super-polynomial time to be solved, e.g. O(n!) or O(nn). To proove that a problem is intractable a proof (super-polynomial lower bound) has to be established as well. For some 2-person games that are played on a n x n board this has been proven.

Class NP Problems

A great example for a non-polynomial computational problem is the Traveling Salesman Problem (TSP). It is not known wheather N = P or N ≠ P, and we don't know where the lower bound of the TSP lies (if it is tractable). The same goes for Kurt Gödel's ≤k-step proof problem, whether there is a proof for a mathematical statement in k or fewer steps, given a set of inference rules and axioms and with k ∈ ℕ.

Traveling Salesman Problem

The normal TSP involves searching a weighted, complete graph, to find the shortest cycle to visit every node once.

The decision TSP looks for a yes or no answer whether there is a cycle that visits every node once with the maximum weight k.

GRAPH THEORY HERE

Classification of Problems

Semi-Decidable

Decision Problems for which there are solutions that halt on some input, and never halt on other inputs.

P

Computational Problems that can be solved in polynomial time, e.g. sorting algorithms.

NP

Decision Problems solvable in non-deterministic polynomial time verified via a certificate/witness in polynomial time.

      To be in NP, a problem needs to be

  • Decision Problem
  • The number of Solutions must be finite and must be of Polynomial lenght
  • If there is a P-lenght solution, it should be verifiable (yes/no)

There are problems that are in NP and maybe in P and maybe in NP-Complete. E.g.: Factoring integers (find a factor k for integer i, such that i = k ⨯ l, with k ≠ i and k ≠ 1). Factoring Integers are in NP, and maybe in P and maybe in NP-Complete. These kind of NP problems fall in between the sets of P and NP-complete, as can be seen here:

np-complete

NP-Hard

Non-decidable decision problems. Eihter in NP or not in NP, e.g. the Halting Problem is not in NP.

If a NP-Hard problem belongs to NP, it is called NP-complete.

NP-complete

A NP-complete problem is NP-Hard and is in NP. Reducable to a NP-problem with a non-deterministic algorithm in polynomial time, e.g. SAT to 3-SAT (SAT = Boolean satisfiability problem)

SAT is NP-Complete. See Cook's Theorem in The Complexity of Theorem-Proving Procedures and Cook's Theorem revisted on Page 38 in Garey / Johnson Computers and Intractability.

If a tractable algorithm would be found for one single NP-complete problem, it would be a solution for all problems in NP. But as it stands, the majority of scientists believe N ≠ NP and a tractable solution for NP problems can never be found.

Cogito ergo sum

Diff (NP-hard) > Diff (NP-Complete)

NP-Complete Problems

Satisfiable propositional logic formulas, short SAT are NP-Complete.

Well-formed Formula that are conjunctions of disjunctions, are in conjunctive normal form CNF:

(P \/ Q) /\ (R \/¬S) (2CNF)

If above 2CNF SAT has an interpretation for which it is TRUE, we call this satisfiable.

"In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A formula is valid if all interpretations make the formula true. The opposites of these concepts are unsatisfiability and invalidity, that is, a formula is unsatisfiable if none of the interpretations make the formula true, and invalid if some such interpretation makes the formula false"

— Wikipedia

Reduction

Making the input from one Decision Problem compatible as input to another decision problem is called reduction.

dpA(x) = dpB(x')

A CNF SAT is reducable in polynomial time to a 3CNF SAT through Karp-reduction. It means splitting a SAT into halfes and adding a propositional value in one half and a negation of that value in the other half.

(¬S \/ T \/ R \/ W ) = (¬S \/ T \/ Z) /\ (R \/ W \/ ¬Z)