Lecture notes for the following lecture:

#### Computational Complexity.

- P, EXP, R
- Most problems are uncomputable
- Hardness and Completeness
- Reduction

There are three complexity classes, classified into:

- P — Polynomial time
- EXP — Exponential time (2^n)^c ( where c = 1.…n). 2^n included.
- R — Problems solvable in Finite time — ** Recursive (meant something else in 1930’s). Think super-recursion.

Most problems can be solved in EXP. All P can be solved in EXP. It is a lot of time. R stands for finite problems, and what is computable problems.

Diagram

Examples (Boolean answer):

- Negative weight cycle detection (in P)
- Given a graph, find if it has any negative weight cycle. (Bellman Ford). Solvable in O(VE) time reachable from S. It is also in EXP, anything you can solve in P can also be solvable in EXP.

- NxN chess (in EXP) (not in P)
- Given NxN board and a current snapshot of a game. Find out if white will win. Play out all possible strategies to find.
- Computational complexity is all about order of growth, so 8x8 takes a lot of time.
- A lot of games are in this category.

- Tetris (in EXP) (don’t know if in P)
- Can you survive given a sequences of pieces and a snapshot of the board.
- known input structures + pseudo-random-generator

- Halting problem: Given a computer program, does it ever halt/stop running? (not in R)
- Given any general problem — will it halt or return a result? You can find this out by actually running the problem, but that cannot be done in R. This is helpful to find out if your algorithm will ever terminate.

15:11 — Proof - Most decision problems are uncomputable (not in R)

The whole field of computational complexity revolves around the decision problem. These are the problems where the answer is YES or NO. You can take any problem and reduce it to a decision problem.

**- programs**

~~ binary string

~~ all binary strings can represented as a natural number in N. (Big Integer)

**- decision: input**

~~ binary string in N

~~ {YES, NO}

~~ { 1 , 0 }

DIAGRAM

So a decision problem can be represented as a TRUTH TABLE of all answers. Where input can be 0, 1, 2, 3, 4, 5.….…n and the answer can be 0 or 1 for each input.

Decision problem is an infinite string of bits ® and a program is a finite (N) string of bits.

Decision problem (in R) so |R| » |N|

R (number of real numbers) (uncountably infinite) is N (number of integers) (countably infinite)

So, this is bad news — that there are too many problems than there are programs to solve them. Almost every problem unsolvable by any program.

Mathematically — all problems that you could think of are unsolvable.

Dynamic programming and NP has something in common “guessing”.

**NP — Non-deterministic polynomial time:**

Solvable in polynomial time via a “lucky algorithm”. The dynamic programming makes guesses for all possible combinations while a “**lucky algorithm**” makes a right guess at every step (of **decision**) along the lines (as its lucky).

**Non-deterministic model:**

This is not a realistic computational model, but nonetheless it is a computational (theoretical/hypthetical) non-deterministic model.

–Algorithm makes guesses and says yes or no. Guaranteed to lead to YES if possible. Imagine the space of guesses. On the path of execution it makes a guess as YES which is luck.

**TETRIS (in NP)**

- Should I drop the pieces, here-here-here-or-here

– Should I rotate left-right-top-bottom.

– Polynomial number of guesses to be made at each step.

Problem: Can I survive?

In the non-deterministic model is a decision problem — where at each step it makes the right answer. If there is anyway to get a YES answer the Non-deterministic model will find it.

**TEST-ABILITY: Another way to think about NP**

Decision problems with “solutions” that can be “checked” in polynomial time.

– When answer = YES

– Can prove it (not in polynomial time)

– Check proof in polynomial time (has to happen in polynomial time)

**Story:** A good tetris player claims that he is “NP Complete” — what he really meant is that he is “lucky” and in the non-deterministic model, he is lucky and the way to prove that is by playing the game, and can survive the sequence of moves.

Every problem you can solve in Polynomial time can also be “checked” or “tested” in polynomial time. You can just solve it and check if you got the right answer.

Millenium-problem (Million-dollar) question

**P != NP**: Big conjecture

- P — are the problems that can be solved in computer.
- NP — can be solved in magical fairy computer.

NP is obviously a more powerful model than P, but we don’t know how to prove it yet.

- You cannot engineer “luck”.
- Cannot built luck on a regular computer. It can be imagined or believed in.

- Generating (proofs of) solutions can be harder than checking them.

Tetris (in NP — P), it could be empty set. Tetris is hardest problem in (NP — P) and (not in P). There are many decision problems in NP — P.

Why?? Tetris is NP-hard.

NP-hard = As hard as every problem in NP. Atleast as hard as every problem in NP.

Tetris is NP-complete.

NP-complete = NP-hard (intersect) NP-complete.

#### (41:00)Reduction

Reductions are a way to design algorithms. You have a problem, you convert into a known problem, and you solve that known-problem and you’re done. It is to convert a problem A into a problem B, that you know how to solve. Examples include:

- Unweighted shortest paths given only Djkstra. (Set all weights to 1 or a consistent constant). Reducing unweighted shortest paths to weighted shortest path.
- Min-product path — shortest paths. We know a known problem to solve the problem with sum of all paths. Reduce the problem by taking logs. LOG(A) + LOG(B) = LOG (AB)
- Longest path –> Negate the weights (and use Bellman ford) to find the longest path.

Reductions are the best algorithm design technique, and also a power technique to prove something like Tetris is NP-Hard.

3-partition problem: Given n numbers, can you divide the numbers into 3-groups where all sum-up-to the same value.

3-partition –> (can be reduced to) Tetris.

The first problem to be proved NP-complete was circuit satisfiability problem.

Karp (in 1970s paper) has already proved that 3-partition problem is NP-complete. This is the idea of standing on the shoulder of the giants).

If we can prove that tetris is “harder” than 3-partition problem, we prove that Tetris is NP-Hard. By harder, we mean that if we are able to reduce a problem A –> B, then B is at least as hard as A.

**Similarly all the NP-complete problems can be reduced to each other.**

#### (49:00) NP-complete problems

- Traveling salesmen problem. (Shortest path that visits all the vertices)
- Longest Common Subsequence (for n strings) — not just two.
- Minesweeper or Sudoku
- SAT (Satisfiability)
- Is there sum setting of variables that results in true. A and B = TRUE (SAT), but A (and NOT) A = TRUE.

- 3D — Shortest path. (Good thing that we’re on the ground)
- Knapsack