<p>I wonder what is known about the implications of <span class="math-container">${\sf AM} = {\sf NP}$</span>?  For example, would that imply <span class="math-container">${\sf BPP} = {\sf P}$</span>?  Any other interesting implications that one would consider counterintuitive perhaps?</p>

CC BY-SA 4.0
2024-12-24T05:14:52.720Z
GI (or even Tensor Iso) in coNP. I find the existence of a poly-time witness that two graphs (or tensors) aren't isomorphic pretty surprising, but I'm not sure if that's in the vein of what you're looking for (hence a comment rather than answer).
Joshua Grochow
CC BY-SA 4.0
2024-12-24T06:20:24.697Z
@JoshuaGrochow Thank you.  Yes, I do know that.  I guess I am also not very surprised given Babai's quasi-polynomial time.  In fact, according to Gasarch's last poll fully 70% of "experts" believe GI is in P...  https://dl.acm.org/doi/10.1145/3319627.3319636
Igor Pak
CC BY-SA 4.0
2024-12-25T23:17:50.453Z
@IgorPak: For Tensor Iso (or even the "easier", by reduction, problem of Code Equivalence), quasi-poly is not known, yet it's still in coAM. The best known for CodeEq is $2^n$ (also due to Babai, but totally different result), and the best known for TI over F_p is $p^{n^{3/2}}$ (Ivanyos-Mendoza-Qiao-Sun-Zhang FOCS '24).
Joshua Grochow
CC BY-SA 4.0
2024-12-26T04:42:00.957Z
@JoshuaGrochow  I see.  Thanks, I did not know.  But is there any reason to believe that CodeEq is NP-hard for example?
Igor Pak
CC BY-SA 4.0
2024-12-26T05:54:24.747Z
@IgorPak: No. Precisely because all of these problems are in coAM, they are not expected to be NP-hard (if they were, PH collapses to its second level, as with any problem in coAM). However, I will note that solve TI over F_p in time $p^{O(n)}$ is equivalent to solving Group Iso for p-groups of class 2 and exponent p in poly(|G|) time. Putting TI into poly(n) time would put iso for those p-groups into poly(log|G|) time (or really, poly time in an appropriately succinct input model) - that is just *so way far* beyond what we currently know...not impossible, but....
Joshua Grochow
<cc.complexity-theory><reference-request><complexity-classes><derandomization><interactive-proofs>
AM=NP implications
Igor Pak
# AM=NP implications

(Asked by: username_0 on 2024-12-23)

I wonder what is known about the implications of ${\sf AM} = {\sf NP}$? For example, would that imply ${\sf BPP} = {\sf P}$? Any other interesting implications that one would consider counterintuitive perhaps?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, derandomization, interactive-proofs

> **Comments:**
> **username_1**: GI (or even Tensor Iso) in coNP. I find the existence of a poly-time witness that two graphs (or tensors) aren't isomorphic pretty surprising, but I'm not sure if that's in the vein of what you're looking for (hence a comment rather than answer).  
> **username_0**: @JoshuaGrochow Thank you.  Yes, I do know that.  I guess I am also not very surprised given Babai's quasi-polynomial time.  In fact, according to Gasarch's last poll fully 70% of "experts" believe GI is in P...  https://dl.acm.org/doi/10.1145/3319627.3319636  
> **username_1**: @IgorPak: For Tensor Iso (or even the "easier", by reduction, problem of Code Equivalence), quasi-poly is not known, yet it's still in coAM. The best known for CodeEq is $2^n$ (also due to Babai, but totally different result), and the best known for TI over F_p is $p^{n^{3/2}}$ (Ivanyos-Mendoza-Qiao-Sun-Zhang FOCS '24).  
> **username_0**: @JoshuaGrochow  I see.  Thanks, I did not know.  But is there any reason to believe that CodeEq is NP-hard for example?  
> **username_1**: @IgorPak: No. Precisely because all of these problems are in coAM, they are not expected to be NP-hard (if they were, PH collapses to its second level, as with any problem in coAM). However, I will note that solve TI over F_p in time $p^{O(n)}$ is equivalent to solving Group Iso for p-groups of class 2 and exponent p in poly(|G|) time. Putting TI into poly(n) time would put iso for those p-groups into poly(log|G|) time (or really, poly time in an appropriately succinct input model) - that is just *so way far* beyond what we currently know...not impossible, but....  

---

## 0 answers

