> For the complete documentation index, see [llms.txt](https://notes.dizy.cc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.dizy.cc/fundamental-algorithms/np-complete.md).

# NP Complete

## Polynomial Reducibility

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

$$
A \leqslant^P B
$$

To prove this relationship, we need:

* Construct an input $$I\_B$$ for B according to input $$I\_A$$ of A (be creative, your goal is the next bullet point). Get the result of B: $$O\_B$$.
* Show that we can get the desired output $$O\_A$$ from $$O\_B$$.