Definition. Polytime Reduction [polytime-reduction]

Definition 1. Polytime Computable [polytime-computable]

For some function $f:\Sigma \ast \rightarrow\Sigma \ast$ , it is polytime computable if there exists a Turing machine that when given $x$ as input terminates with $f(x)$ on the tape and runs in time $\text{poly}\left( |x| \right)$ .

Let $A,B \subseteq \Sigma \ast$ (Let $A$ and $B$ be languages). $f$ is a polytime reduction from $A$ to $B$ if:

$f$ is a polytime computable function
$x \in A\Rightarrow f(x) \in B$ ( $f(A) \subseteq B$ )
$x \notin A\Rightarrow f(x) \notin B$ ( $f(A^{\_} \subseteq B^{\_}$ )

We then may say $A\underset{P}{\leq}B$ .

…helpful image…

Example. Polytime Reduction

Suppose $A = \left\{ {0^{n}10^{n}:n \geq 0} \right\}$ , and $B = \left\{ {1^{n}01^{n}:n \geq 0} \right\}$ . Claim: $A\underset{P}{\leq}B$

What does this mean? It means there exists some function that can take a string, map it, and manipulate it so that if $x \in A$ , then $x \in B$ , and same for converses.

Proof.

Let $f$ be the function that flips the bits of its input. Then, we’re done.

$x \in A\Rightarrow f(x) \in B$
$x \notin A\Rightarrow f(x) \notin B$
$f(x) \in B\Rightarrow x \in A$
$x \in A\Leftrightarrow f(x) \in B$
Note: these do not need to be bijections!
- A reduction that simply sends all satisfiable inputs to 0 is fine.

Reductions are helpful!

Method: find a way to map:
- yes-instances of $P_{1}$ to yes-instances of $P_{2}$
- no-instances of $P_{1}$ to no-instances of $P_{2}$
Notation: $P_{1}\underset{P}{\leq}P_{2}$
Logic: if $P_{2}$ is easy, $P_{1}$ is easy
Contrapositive: if $P_{1}$ is hard, $P_{2}$ is hard

Theorem.

If $A\underset{P}{\leq}B$ and $B \in P$ , then $A \in P$ .

There is a polytime Turing machine N that decides $B$ .
There is a polytime reduction $f$ from $A$ to $B$ .

Proof.

We want a Turing machine $M$ that decides $A$ in polynomial time.

On input $x$ : compute $z = f(x)$ and then simulate $N$ on input $z$ . Accept iff $N$ accepts.
If $x \in A\Rightarrow f(x) \in B\Rightarrow N\ \text{accepts}$ .
If $x \in A^{\_}\Rightarrow f(x) \notin B\Rightarrow N\ \text{rejects}$ .

Question. If we know $A$ reduces to $B$ and $B$ is in $\text{NP}$ , is $A$ in $\text{NP}$ ?

Answer. Yes, $\text{P}$ is a subset of $\text{NP}$ . Mind the direction!

When we talked about Turing machines, we had a notion of what it meant to be hard: undecidability. But now we’re talking about NP. So which problems in NP are hard?

Maybe $\text{P} = \text{NP}$ , and so all problems in NP are easy.