/ computer science

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(?)

/\ /\ /<br>
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.


Classification of Problems


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


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


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:



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.


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


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)

Computational Complexity
Share this