Question

Let $A\subseteq 1^{*}$ be any unary language. Show that if A is NP-complete, then P = NP. (Hint: Consider a polynomial time reduction f from SATto A. For a formula $\varphi$, let ${\varphi }_{0100}$be the reduced formula where variables x1, x2, x3, and x4 in$\varphi$ are set to the values 0, 1, 0, and 0, respectively. What happens when you apply f to all of these exponentially many reduced formulas?)

Short answer

There are at most $n.p\left(\right|\varphi \left|\right)\le \left|\varphi \right|.p\left(\right|\varphi \left|\right)$nodes on any $f\left({\varphi }_v\right)\le p\left(\right|\varphi \left|\right)$such path, and there are at most nodes on any for all $v\in V$.

Step-by-step solution

NP Class

A nondeterministic turning machine assigns a problem to the NP (nondeterministic polynomial time) class if it can be solved in polynomial time.

Explanation

Let A be the unary NP complete language that satisfies the condition $\varphi \in SAT\iff 1^{f\left(\varphi \right)}\in A$. The formula for calculating $1^{f\left(\varphi \right)}$the amount of time required is $p\left|\varphi \right|$. Let $T=\left(V,E\right)$be a satisfiable call tree for an input formula. For example $v\in V$, consider $\varphi$be the V formula with an argument.

Consider two nodes $v,v\text{'}$neither of which is an ancestor of the other. At the time of the v' call, it is known whether $p\left|\varphi \right|$is satisfiable, therefore the hashmap is defined for $f\left({\varphi }_v\right)$ . As a result $f\left({\varphi }_v\right)=f\left({\varphi }_{v\text{'}}\right)$ . There are at most n nodes on any such path., and there are at most $n.p\left(\right|\varphi \left|\right)\le \left|\varphi \right|.p\left(\right|\varphi \left|\right)$ nodes on any $f\left({\varphi }_v\right)\le p\left(\right|\varphi \left|\right)$ for all $v\in V$.