<p>Being an enthusiast in computational complexity theory, I recently came across with this wonderful work <a href="https://www.scottaaronson.com/papers/alg.pdf" rel="nofollow noreferrer">Algebrization: A New Barrier in Complexity Theory</a>.</p>
<p>My question is about Theorem 5.3 in it (pp. 23-24).</p>
<p>It states that &quot;there exists an oracle <span class="math-container">$A$</span> and an algebrization <span class="math-container">$\tilde{A}$</span> of <span class="math-container">$A$</span> such that <span class="math-container">$\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$</span>. Furthermore, the language <span class="math-container">$L$</span> that achieves this separation simply corresponds to deciding, on input length <span class="math-container">$n$</span>, whether there exists a <span class="math-container">$w\in\{0,1\}^n$</span> with <span class="math-container">$A_n(w)=1$</span>.&quot;</p>
<p>The basic idea of its proof is to consider the oracle <span class="math-container">$A$</span> as a Boolean function <span class="math-container">$A_n:\{0,1\}^n\rightarrow \{0,1\}$</span>, while <span class="math-container">$\tilde{A}$</span> is a multi-quadratic extension <span class="math-container">$\tilde{A}_{n,\mathbb{F}}:\mathbb{F}^n\rightarrow \mathbb{F}$</span> of <span class="math-container">$A$</span> over the finite field <span class="math-container">$\mathbb{F}$</span>. Now, they define the language, <span class="math-container">$$L=\{1^n \mid \exists w\in\{0,1\}^n \land A_n(w)=1\}.$$</span> For all <span class="math-container">$A$</span>, <span class="math-container">$L\in\mathbf{NP}^A$</span>. Now, they construct <span class="math-container">$\tilde{A}$</span> in such a way so that <span class="math-container">$L\notin \mathbf{P}^\tilde{A}$</span>.</p>
<p>Therefore, it says that <strong>there exists</strong> an algebrization (i.e., <span class="math-container">$\tilde{A}$</span>) which shows the separation <span class="math-container">$\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$</span>. So, they infer that we need non-algebrization in order to prove <span class="math-container">$\mathbf{NP}\subset\mathbf{P}$</span>. But does this theorem prove that <strong>for all</strong> algebrization <span class="math-container">$\tilde{A}$</span> (w.r.t. <span class="math-container">$A$</span>) we have, <span class="math-container">$\mathbf{NP}^A\not\subset\mathbf{P}^\tilde{A}$</span>? More specifically, how to refute the existence of at least one algebrization <span class="math-container">$\tilde{A}$</span> that may prove <span class="math-container">$\mathbf{NP}^A\subset\mathbf{P}^\tilde{A}$</span>?</p>

CC BY-SA 4.0
2023-08-25T16:04:39.687Z
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.
Souvik
CC BY-SA 4.0
2023-08-25T18:13:33.137Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-08-27T15:28:35.363Z
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$.
Souvik
CC BY-SA 4.0
2023-08-27T15:41:18.483Z
Further, Theorem 5.1 and 5.3 do not contradict each other unless their proofs use the same algebrization, say $\tilde{A}$. Even if they, it would mean that $\mathbf{P}$ vs. $\mathbf{NP}$ is unsolvable using that particular $\tilde{A}$. How to refute the existence of another algebrization, say $\tilde{B}$, that contradicts Theorem 5.3 but admits to Theorem 5.1?
Souvik
CC BY-SA 4.0
2023-08-30T16:41:48.903Z
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. ...
Emil Jeřábek
CC BY-SA 4.0
2023-08-30T16:48:52.580Z
... 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".
Emil Jeřábek
<complexity-classes><time-complexity>
How "Algebrization" is "A New Barrier in Complexity Theory"?
Souvik
# How "Algebrization" is "A New Barrier in Complexity Theory"?

(Asked by: username_0 on 2023-08-22)

Being an enthusiast in computational complexity theory, I recently came across with this wonderful work [Algebrization: A New Barrier in Complexity Theory](https://www.scottaaronson.com/papers/alg.pdf).

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}$?

**Tags:** complexity-classes, time-complexity

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_0**: Further, Theorem 5.1 and 5.3 do not contradict each other unless their proofs use the same algebrization, say $\tilde{A}$. Even if they, it would mean that $\mathbf{P}$ vs. $\mathbf{NP}$ is unsolvable using that particular $\tilde{A}$. How to refute the existence of another algebrization, say $\tilde{B}$, that contradicts Theorem 5.3 but admits to Theorem 5.1?  
> **username_1**: 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. ...  
> **username_1**: ... 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".  

---

## 0 answers

