📘
📘
📘
📘
Notes
Fundamental Algorithms
Search
⌃K
Links

NP Complete

Polynomial Reducibility

When A is polynomial-reducible to B, we denote this relationship as:
A⩽PBA \leqslant^P B
To prove this relationship, we need:
  • Construct an input
    IBI_B
    for B according to input
    IAI_A
    of A (be creative, your goal is the next bullet point). Get the result of B:
    OBO_B
    .
  • Show that we can get the desired output
    OAO_A
    from
    OBO_B
    .
Last modified 10mo ago