šŸ“˜
Notes
Blog
Fundamental Algorithms
Fundamental Algorithms
  • Overview
  • Introduction
  • Recurrences
  • Search Trees
  • Dynamic Programming
  • Shortest Paths
  • NP Complete
Powered by GitBook
On this page

NP Complete

PreviousShortest Paths

Last updated 2 years ago

Polynomial Reducibility

When A is polynomial-reducible to B, we denote this relationship as:

A⩽PBA \leqslant^P BA⩽PB

To prove this relationship, we need:

  • Construct an input IBI_BIB​ for B according to input IAI_AIA​ of A (be creative, your goal is the next bullet point). Get the result of B: OBO_BOB​.

  • Show that we can get the desired output OAO_AOA​ from OBO_BOB​.