NP Complete

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​
.

Shortest Paths

Last modified 10mo ago