Computational Complexity
Complexity Classes
The Computational Zoo is far more subtle and complex than I thought it was.
It contains P, NP (+complete), EXP, NP-hard, CO-NP (+complete), PSPACE, BPP, BQP, EXPSPACE, 2-EXP, halting problem, decidable, etc!
Big Oh Notation
TODO
NP-Hard and NP-Complete
If \(P=NP\), then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps', no fundamental gap between solving a problem and recognising the solution once it's found. Everyone that could appreciate a symphony would be Mozart, everyone who could follow a step-by-step argument would be Gauss"-Scott Aaronson
TODO main diagram.
This topic usually concludes a course on algorithms, and for good reason.
At this stage we possess a potpourri of algorithmic methods; ranging from \(O(n)\) to \(O(n^n\) time. If in your mind you did not read this as "Oh of N time", then you ought to go back to the Big Oh Notation section.
Roughly we can chalk up a table of polynomial time methods and non-polynomial time methods – i.e. exponential time methods
| Polynomial Time | Exponential Time |
| Linear Search (O(n)) | 0/1 Knapsack (O(2^n)) |
| Binary Search (O(log(n))) | Travelling Salesman(O(n!)) |
| Insertion Sort (O(n^2)) | Sum of Subsets (O(2^n)) |
| MergeSort (O(nlog(n))) | k-Graph Colouring (O(k^n)) |
| Matrix Multiplication (O(n^3)) | Hamiltonian Cycle (O(n!)) |
| … | … |
From here, we would realistically like to convert all our Exponential Time Algorithms into Polynomial Time algorithms. However, doing so for each individual problem is labouriously infeasible ⊕ . As such, we ought to determine the common thread/s between all of our exponential time problems and then try our hardest to convert this base problem into polynomial time.
Satisfiability
Notation
Simply, we can consider any CNF (Conjunctive Normal Form) of \(n\) variables: \(x_1, x_2, ..., x_n\): \[ (x_1 \lor x_2 ) \land (x_3 \lor \neg x_1 ) \] Here \(n=3\), and the Conjunctive Normal Form means that sequences of brackets are formed with disjunction operators and conjunction operators are used between those.
\[ (x_1 \lor x_2) \land (\neg x_3 \lor x_4 \lor x_5)\quad\text{another example} \] notice that the \(\lor\) is always between the decision variables in the brackets.
Problem
The problem is finding the values of the decision variables such that the CNF equates to True.
Considering a couple of examples, we can see that with \(n=2\) \[x_1 \land \neg x_2 \] Is indeed satisfiable:
| \(x_1\) | \(x_2)\ | \(\neg x_2\) | \(x_1 \land \neg x_2\) |
| T | T | F | F |
| T | F | T | T |
| F | T | F | F |
| F | F | T | F |
The second row satisfies the logical expression. You must also quickly realise that for us to come to this conclusion we had to search all 4 rows — i.e. all \(2^2\) combinations.
In general it is true that to determine the truth value we had to consider \(2^n\) possibilities.
For completeness, let us check the satisfiability of "a and not a":
| \(a)\) | \(\neg a\) | \(a \land \neg a\) |
| T | F | F |
| F | T | F |
| T | F | F |
| F | T | F |
Thus "a and not a" is unsatisfiable.
Non-Deterministic Polynomial Time
It is worth just quickly jab stepping in the sand and attacking this problem from a different angle — all the whilst – keeping an eye on the prize.
If you can't write Polynomial Time algorithms, then why don't you just write Non-Deterministic Poylnomial Time algorithms?
What this means is that, for the above exponential time algorithms, it's not like every line is exponential in time-complexity. It would just be a select few lines. And in honour of trying to reduce these problems to their essence (as we did above by finding the archetypal exponential problem CNF-SAT), we can rewrite an exponential algorithm such as:
Algorithm NSearch(A,n,key)
{
j=choice();
if(key=A[j])
{
write(j);
success();
}
write(0);
failure();
}
Here the Non-deterministic parts of the above algorithm would be choice(), success() and failure(), and so a usually \(O(n)\) time algorithm is converted to \(O(1)\) constant time.
Polynomial Time
The principle of the above point is ad nihil redactus; to reduce towards zero, the non-deterministic segments of the code.
A couple notable examples of such NP-hard problems which eventually become part of the P Class are:
- Linear Programming
- Maximum Flow
- Perfect Matching in Bipartite Graphs
- Primality Testing
- Graph Isomorphisms
TODO Graphic
NP-Hard
If instances of an exponential-time algorithm are congruent with instances of the CNF-SAT problem, then the problem in question would be "NP-Hard".
NP-Complete
When you can actually write a Non-deterministic Polynomial Time for the problem in question – same as Figure 1
NP Second Definition
Technically speaking, a Mathematically equivalent, but different way of defining these problems (defined above as a means for ad nihil redactum), is that:
"Given a solution to the exponential-time problem, you can at least verify the solution in Polynomial time".
A good example of this is Sudoku. Solving the game would require an exponential time algorithm, but verifying the correctness of a solution can be done in polynomial time.
Cook-Levin Theorem
If the Satisfiable Problem is in P, then \(P=NP\).