📘
📘
📘
📘
Notes
Fundamental Algorithms
Blog
Search
⌃K
Links
Fundamental Algorithms
📘
📘
📘
📘
Notes
Fundamental Algorithms
Search
⌃K
Overview
Introduction
Recurrences
Search Trees
Dynamic Programming
Shortest Paths
NP Complete
Powered By
GitBook
NP Complete
Polynomial Reducibility
When A is polynomial-reducible to B, we denote this relationship as:
A
⩽
P
B
A \leqslant^P B
A
⩽
P
B
To prove this relationship, we need:
Construct an input
I
B
I_B
I
B
for B according to input
I
A
I_A
I
A
of A (be creative, your goal is the next bullet point). Get the result of B:
O
B
O_B
O
B
.
Show that we can get the desired output
O
A
O_A
O
A
from
O
B
O_B
O
B
.
Previous
Shortest Paths
Last modified
10mo ago