NP-Completeness

Table of Contents

Overview

  • NP = non-deterministic polynomial
  • Decision problems
  • NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs
    • More precisely, efficiently means by deterministic computations that can be performed in polynomial time

Classes

NP

NP-Complete

  • Decision problem which is NP and NP-hard
  • A given solution to an NP-complete problem can be verified in polynomial time, there is no known efficient (i.e. polynomial time) method for finding a solution in the first place!
    • Therefore NP-complete problems are most of the time addressed by heuristic methods and approximation algorithms.

NP-Hard (non-deterministic polynomial acceptable problems)

Oooh, so NP-hard says that if we solve this problem, any NP problem can be solved in polynomial time, using this solution as a subroutine!

Assuming a solution for the NP-hard problem H takes 1 unit time, we can use the H 's solution to solve any NP problem L in polynomial time.

  • "At least as hard as the hardest problems in NP"
  • A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H

Definitions

deterministic turing machine (DTM)
set of rules prescribes at most one action to be performed for any given situation. TL;DR: can only choose from one actions given the current state.
non-deterministic turing machine (NTM)
may have a set of rules that prescribes more than one action for any given situation. TL;DR: can potentially choose from multiple actions given the current state.