0
$\begingroup$

My teacher said in his lecture( followed by the book Barak and Arora) the following:

We will imagine that a shocking discovery reveals that there exists a function $f$, thinking in linear time, so that for every input of the form $\langle G, k\rangle$ there exists: $$f(\langle G, k\rangle)\in \texttt{INDSET} \longleftrightarrow \langle G, k\rangle \in \texttt{INDSET}$$ that is, $f$ is Reduction from $\texttt{INDSET}$ to itself.

In addition, it holds that for each input $\langle G, k\rangle$ the output of the reduction $f(\langle G, k\rangle) = \langle G', k'\rangle$ satisfies $k'\leq 3.\log(|V'|),$ as $G'=(V',E').$

My question: I need the explaination what the sensational (imagined) discovery means about the classes $\text{P, NP,}$ and the connections between them Compared to what we learned in the computational complexity course. How to justify our answer?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The existence of an independent set of size $k=O(\log n)$ can be checked in quasipolynomial time $n^{O(k)}=n^{O(\log n)}$, thus the existence of such a reduction would imply that $\mathrm{NP\subseteq DTIME}(n^{O(\log n)})\subseteq\mathrm{QP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.