# 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(n ^{c})*. 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(n^{n}). 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 TSPlooks for a yes or no answer whether there is a cycle that visits every node once with the maximum weightk.

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-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.

*dp _{A}(x) = dp_{B}(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)*