1
$\begingroup$

Being an enthusiast in computational complexity theory, I recently came across with this wonderful work Algebrization: A New Barrier in Complexity Theory.

My question is about Theorem 5.3 in it (pp. 23-24).

It states that "there exists an oracle $A$ and an algebrization $\tilde{A}$ of $A$ such that $\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$. Furthermore, the language $L$ that achieves this separation simply corresponds to deciding, on input length $n$, whether there exists a $w\in\{0,1\}^n$ with $A_n(w)=1$."

The basic idea of its proof is to consider the oracle $A$ as a Boolean function $A_n:\{0,1\}^n\rightarrow \{0,1\}$, while $\tilde{A}$ is a multi-quadratic extension $\tilde{A}_{n,\mathbb{F}}:\mathbb{F}^n\rightarrow \mathbb{F}$ of $A$ over the finite field $\mathbb{F}$. Now, they define the language, $$L=\{1^n \mid \exists w\in\{0,1\}^n \land A_n(w)=1\}.$$ For all $A$, $L\in\mathbf{NP}^A$. Now, they construct $\tilde{A}$ in such a way so that $L\notin \mathbf{P}^\tilde{A}$.

Therefore, it says that there exists an algebrization (i.e., $\tilde{A}$) which shows the separation $\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$. So, they infer that we need non-algebrization in order to prove $\mathbf{NP}\subset\mathbf{P}$. But does this theorem prove that for all algebrization $\tilde{A}$ (w.r.t. $A$) we have, $\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$? More specifically, how to refute the existence of at least one algebrization $\tilde{A}$ that may prove $\mathbf{NP}^A\subset\mathbf{P}^\tilde{A}$?

Improve this question
$\endgroup$
6
  • $\begingroup$ Exactly. Thank you for this explanation. But it is not me rather the authors who inferred that "The second set of results shows that, for many basic complexity questions, any solution will require non-algebrizing technique" (pp. 3). Clearly this may not be the case. $\endgroup$
    – Souvik
    Aug 25 at 16:04
  • 3
    $\begingroup$ You seem to be missing something quite basic about the logic of the argument. The conclusion of the authors is perfectly correct. Any algebrizing technique that resolves the NP vs. P question will in fact show that $\mathrm{NP}^{\tilde A}\nsubseteq\mathrm P^{\tilde A}$ for all $A$, or that $\mathrm{NP}^A\subseteq\mathrm P^{\tilde A}$ for all $A$. Since there are counterexamples showing that both these statements are false, no algebrizing technique can resolve the NP vs. P question. $\endgroup$
    – Emil Jeřábek
    Aug 25 at 18:13
  • 1
    $\begingroup$ This is exactly what my question was. Can you kindly specify which theorem says that "any algebrizing technique shows that $\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$? Theorem 5.3 does not do this. The extension $\tilde{A}$ of $A$ in Theorem 5.3 talks about a particular algebrization. In order to prove the separation for any algebrization, it must consider all efficiently computable algebrization. However, Theorem 5.1 correctly says that $\mathbf{NP}^\tilde{B}\subset\mathbf{P}^B$ for any algebrization. Its proof is independent of any particular algebrization of $B$. $\endgroup$
    – Souvik
    Aug 27 at 15:28
  • 2
    $\begingroup$ Theorems 5.1 and 5.3 are both theorems, hence it would be very, very, very bad if they contradicted each other. Again, you seem to misunderstand the definition of the concepts. If $\let\R\mathrm\def\tA{\tilde A}\R{NP\subseteq P}$ can be proved by a technique that algebrizes, then by definition this means that $\R{NP}^A\subseteq\R P^\tA$ for all $A$ and all low-degree extensions $\tA$. But this is false, since there exist $A$ and $\tA$ such that $\R{NP}^A\nsubseteq\R P^\tA$ by Thm. 5.3. Thus, the premise fails: $\R{NP\subseteq P}$ cannot be proved by a technique that algebrizes. ... $\endgroup$
    – Emil Jeřábek
    Aug 30 at 16:41
  • 2
    $\begingroup$ ... Likewise: if $\let\R\mathrm\def\tA{\tilde A}\R{NP\nsubseteq P}$ can be proved by a technique that algebrizes, then by definition this means that $\R{NP}^\tA\nsubseteq\R P^A$ for all $A$ and all $\tA$. But this is false, since there exist $A$ and $\tA$ such that $\R{NP}^\tA\subseteq\R P^A$ by Thm. 5.1. Thus, the premise fails: $\R{NP\nsubseteq P}$ cannot be proved by a technique that algebrizes. Putting the two together: no technique that algebrizes can resolve the NP vs. P question either way. This is the "barrier". $\endgroup$
    – Emil Jeřábek
    Aug 30 at 16:48

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.