Skip to content

Complexity

Overview

  • Complexity classes are a way of categorizing problems by difficulty
  • There are two kind of problems: search and verification problems

Example: Sorting

  • Search version: input a list of numbers X and output same list in sorted order (call it Y)
  • Verification version: input a list of numbers X and another list Y, and output "YES" if Y is sorted version of X, "NO" otherwise

Classes

P

  • Problems are in this class, if there exists a PTIME (polynomial-time, runs in \(O(f(n))\), where \(f\) is polynomial) algorithm that solves the problem

NP

  • Problems are in this class, if there exists a PTIME algorithm, that verifies the problem, but are not necessarily solveable in PTIME

Reducibility: Given an instance of a hard problem, we can construct an instance of another problem, whose solution will also solve the first problem

NP-complete

  • If two problems in NP can be reduced to each other, are in this class
  • A solution for any of these would give us a solution to all of these problems

NP-hard

  • These problems are at least as hard as the hardest problem in NP-complete

P vs. NP

Is P=NP?

  • Yes: \(P = NP\) means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well
  • No: \(P \neq NP\) means that it is impossible to find a general algorithm that will correctly and accurately solve an NP-complete problem all the time

References


Last update: November 23, 2020