My field notes on Computation Complexity and what it is.
- Quick Start
- P vs NP
- Polynomial Time
- Who was Cobham and what was his thesis about?
- Polynomials are fast/efficient
- What’s a Polynomial again?
- Example of Valid Polynomials
- What is not a polynomial?
- When we say that polynomial time is considered efficnent, does that mean that non-polynomial time is inefficient?
- What does it mean to be efficient/easily verifiable?
- Turing Machines
Complexity classes give us a way to group problems together based on how hard they are to solve.
Computational Complexity deals with Decision Problems.
- Decision problems result in a
- Is this array sorted?
- Is there a
cliquein this graph?
- Optimization problems concerned with finding the best answer to a particular input.
Complexity and Good Games
Something cool to consider, how do Complexity Classes relate to good games? Are good games NP-hard? Checkout this MIT: Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014).
P vs NP
P problems are quickly solved in polynomial time
NP problems are quickly verified in polynomial time, but not necessarily solved in polynomial time
As an example: Sudoku. Sudoku takes a while to solve, you kinda have to brute force solutions until you get it right. But it’s really easy to verify an answer, so Sudoku is considered
Is [insert sorting/searching algorithm] considered P?
Complexity is used to answer decision problems, and sorting/searching is not considered a decison problem, but is known as a function problem.
What does NP intuitively mean?
Expect a bruteforce solution, maybe an effiecient solution, and an easily verifiable solution.
This association with exponential time confuses some people: they think incorrectly that NP problems require exponential-time to solve (or even worse there are no algorithm for them at all). Stating that a problem is in NP does not mean a problem is difficult to solve, it just means that it is easy to verify, it is an upper bound on the difficulty of solving the problem, and many NP problems are easy to solve since P⊆NP.
Does P == NP?
We might never know.
Who was Cobham and what was his thesis about?
He summarized polynomial time as “tractable”, “feasible”, “efficient”, or “fast”
Polynomials are fast/efficient
A polynomial time algorithm is considered efficient.
Cobham’s thesis states that polynomial time is a synonym for “tractable”, “feasible”, “efficient”, or “fast”.
Depending on the polynomial there could be a more efficient solution. Example: Bubble Sort runs in $O(n^2)$, and is considered polynomial, but is not as efficient as other sorting algorithms, with better run times.
What’s a Polynomial again?
Polynomial meaning: multiple terms
Polynomials consist of:
- Coefficients, variables, constants and exponents
- only addition, subtraction, multiplcation
- no negative exponents
Example of Valid Polynomials
What is not a polynomial?
- negative exponents
- dividing by a variable
- fractional components
- radicals (like sqrt)
When we say that polynomial time is considered efficnent, does that mean that non-polynomial time is inefficient?
What does it mean to be efficient/easily verifiable?
While NP problems may not be efficient to solve, they may have efficient ways to validate their answers.
You can verify the answer in polynomial time, but maybe not fin the solution in polynomial time.
What’s a turing machine again? What isn’t a turing machine?
Deterministic vs non-deterministic turing machines?
deterministic turing machines are like today’s computers
non-deterministic can be thought of as unlimited parallelism
- non-deterministic: a fancy way of talking about guessing a solution
- Problems in NP are still relatively easy: if only we could guess the right solution, we could then quickly test it.
- a way of mathematically formalizing the idea of a brute-force search algorithm
What is NP-Complete?
It’s all about reduction.
An NP complete problem is a problem that other problem in NP reduces to.
A problem $p$ in $NP$ is NP-complete if every other problem in NP can be transformed (or reduced) into $p$ in polynomial time. if we can solve these problems, we can solve any other NP problem and the solutions to these problems can be verified in polynomial time.
NP-complete is both NP and NP-hard
Every NP problem can be solved by an NP-complete problem, and the solution can be verified in polynomial time.
What does “complete” mean in “NP-complete”?
From the world of mathematical/formal logic: “a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system”
“complete” meaning: among the “hardest” (or “most expressive”) problems in the complexity class
“Complete” refers to the property of being able to simulate everything in the same complexity class.
NP-complete was almost named something else. According to this excerpt from wikipedia:
Other suggestions made in the poll included “Herculean”, “formidable”, Steiglitz’s “hard-boiled” in honor of Cook, and Shen Lin’s acronym “PET”, which stood for “probably exponential time”, but depending on which way the P versus NP problem went, could stand for “provably exponential time” or “previously exponential time”.
What are some common NP-complete problems?
subset sum problem
What is NP-Hard?
The hardest of NP problem, nut not necessarily in NP.
Remember NP problems have easily verifiable solutions. If a problem is hard to verify (ex: verify the next best chess move) then it might not be in NP.
NP-complete vs NP-Hard.
What are some common NP-Hard problems?
- Chess (unbounded board)
Is Chess really NP-hard?
The game you buy from the store has a limited board size and so there’s an upper bound on the number of next best moves.
However, on a thoretical boundless chessboard, now you’re talking NP-hard.