Computational Complexity

My field notes on Computation Complexity and what it is.

Quick Start

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 YES or NO response.
    • Is this array sorted?
    • Is there a clique in 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).

Start with this youtube video [P vs. NP and the Computational Complexity Zoo](https://www.youtube.com/watch?v=YX40hbAHx3s)

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

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.

https://cs.stackexchange.com/questions/9556/what-is-the-definition-of-p-np-np-complete-and-np-hard

Does P == NP?

We might never know.

Polynomial Time

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

  • $5$
  • $x$
  • $5x$
  • $5x^2$
  • $5x^2+2y$
  • $5x^2+2y-7$

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.

Turing Machines

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

NP-complete

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[9] 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”.[10]

What are some common NP-complete problems?

subset sum problem

NP-Hard

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?

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

Resources