Computational Complexity

algorithms

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 6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023).

Start with this youtube video P vs. NP and the Computational Complexity Zoo

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 [SORT/SEARCH 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

Cobham’s thesis states that polynomial time is a synonym for “tractable”, “feasible”, “efficient”, or “fast”.

A polynomial time algorithm is considered efficient.

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 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 Polynomial again?

Polynomial meaning: multiple terms

Polynomials consist of:

Coefficients, variables, constants and exponents
only addition, subtraction, multiplication
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)
non-integer exponents - This is important. For some big-o growth trends, you can get exponential growth, something like: 5^x

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.

Brian Wigginton