<p>The paper contains the statement:</p>
<blockquote>
<p>The high-degree terms involving products of <span class="math-container">$x_i$</span> cannot be simplified or linearized without assigning values to <span class="math-container">$x_i$</span>. Due to the multiplicative and recursive nature of the equations, isolating <span class="math-container">$_$</span>
or expressing them in terms of other variables is not feasible,&quot;</p>
</blockquote>
<p>This seems to indicate that he is (probably without realizing it) assuming a very particular type of algorithm for solving the problem. Thus, this paper does not contain a proof that P <span class="math-container">$\neq$</span> NP, and seems very unlikely to lead to one.</p>

CC BY-SA 4.0
2024-12-19T20:18:21.713Z
2024-12-19T20:18:21.713Z
Peter Shor 
<p><a href="https://eprint.iacr.org/2024/2035" rel="nofollow noreferrer">This paper</a> has been put on the IACR eprint today. It claims that a new language, called the Add/XNOR problem, is in <span class="math-container">$\mathsf{NP}$</span> but not in <span class="math-container">$\mathsf{P}$</span>.</p>
<p>Now, I'm clearly not knowledgeable enough to know whether there is an obvious flaw in this paper, but I'm asking this question because I'm interested about which kind of flaws (if any!) could be found in such proofs (and of course, I'm <em>slightly</em> interested about the result :)). I've seen papers claiming similar facts, but were disregarded by the expert community as &quot;obviously flawed&quot;, which got me kind of frustrated: I'd like to know if there is a killing argument like &quot;they claim A in their proof, but A has been shown impossible by Foo et. al&quot;. Something I could easily check and convince me.</p>
<p>Of course, this assumes that the paper is a real tentative and not complete nonsense,but I'm <em>also</em> not knowledgeable enough to see it on the one hand, and the author has a fair number of well-cited papers on the other hand, which makes me think that the probability that this is the case should be quite low.</p>
<p>So, are there obvious flaws allowing to disregard this paper, or is it a serious claim that must be verified by the community?</p>

CC BY-SA 4.0
2024-12-19T13:03:50.080Z
He uploaded a revision within 2 days. If you want to put out a proof to P $\ne$ NP, make sure it's perfect when you put it out.
mathworker21
CC BY-SA 4.0
2024-12-19T13:08:26.183Z
The title of the paper is "A Heuristic Proof of P \neq NP".
Reijo Jaakkola
CC BY-SA 4.0
2024-12-19T13:12:53.807Z
https://scottaaronson.blog/?p=304
Or Meir
CC BY-SA 4.0
2024-12-19T13:44:22.853Z
IMO‌, any correct proof for $P\neq NP$ is verifiable form its abstract, so it seems there is no correct answer according to its abstract!
Mohsen Ghorbani
CC BY-SA 4.0
2024-12-19T15:20:58.943Z
It's not even wrong. Statements like "Theorem 2. The problem p corresponds to a non-linear system, and solving this system is equivalent to an exhaustive search." don't have sense. He is just arguing one type of algorithm must do exhaustive search, nothing close to P vs NP
Ryan Williams
CC BY-SA 4.0
2024-12-19T15:26:48.270Z
@RyanWilliams Why's that not related to P vs NP? If you can prove that the problem is in NP, but that the best possible algorithm is exponential in the input (like, $2^n$ operations), doesn't that give you $P\neq NP$? I'm not saying this is what is shown here (which seems not to be the case, since they don't seem to prove that it actually is the best possible algorithm), I'm just speaking theoretically, wouldn't such a proof solve the question?
Tristan Nemoz
CC BY-SA 4.0
2024-12-19T17:37:26.187Z
Consider the statement *"The high-degree terms involving products of *x_i* cannot be simplified or linearized without assigning values to *x_i*. Due to the multiplicative and recursive nature of the equations, isolating $x_i $ or expressing them in terms of other variables is not feasible,"* At best, he is assuming a particular kind of algorithm here. At worst, this is handwaving. Either way, it's not a rigorous proof of P $\neq$ NP
Peter Shor 
CC BY-SA 4.0
2024-12-27T23:03:26.470Z
Note that there are more authors of papers called Ping Wang. I tried to correct somebody on misidentifying the author only to find out that the page that I found had miscontributed the paper to the wrong Ping Wang itself.
Maarten Bodewes
CC BY-SA 4.0
2024-12-30T08:05:28.900Z
Also see this: https://scottaaronson.blog/?p=458
Or Meir
<cc.complexity-theory><proofs>
Is there an error in the recent $\mathsf{P}\neq\mathsf{NP}$ proof by Ping Wang?
Tristan Nemoz
# Is there an error in the recent $\mathsf{P}\neq\mathsf{NP}$ proof by Ping Wang?

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

[This paper](https://eprint.iacr.org/2024/2035) has been put on the IACR eprint today. It claims that a new language, called the Add/XNOR problem, is in $\mathsf{NP}$ but not in $\mathsf{P}$.

Now, I'm clearly not knowledgeable enough to know whether there is an obvious flaw in this paper, but I'm asking this question because I'm interested about which kind of flaws (if any!) could be found in such proofs (and of course, I'm *slightly* interested about the result :)). I've seen papers claiming similar facts, but were disregarded by the expert community as "obviously flawed", which got me kind of frustrated: I'd like to know if there is a killing argument like "they claim A in their proof, but A has been shown impossible by Foo et. al". Something I could easily check and convince me.

Of course, this assumes that the paper is a real tentative and not complete nonsense,but I'm *also* not knowledgeable enough to see it on the one hand, and the author has a fair number of well-cited papers on the other hand, which makes me think that the probability that this is the case should be quite low.

So, are there obvious flaws allowing to disregard this paper, or is it a serious claim that must be verified by the community?

**Tags:** cc.complexity-theory, proofs
> **Comments:**
> **username_1**: He uploaded a revision within 2 days. If you want to put out a proof to P $\ne$ NP, make sure it's perfect when you put it out.  
> **username_2**: The title of the paper is "A Heuristic Proof of P \neq NP".  
> **username_3**: https://scottaaronson.blog/?p=304  
> **username_4**: IMO‌, any correct proof for $P\neq NP$ is verifiable form its abstract, so it seems there is no correct answer according to its abstract!  
> **username_5**: It's not even wrong. Statements like "Theorem 2. The problem p corresponds to a non-linear system, and solving this system is equivalent to an exhaustive search." don't have sense. He is just arguing one type of algorithm must do exhaustive search, nothing close to P vs NP  
> **username_0**: @RyanWilliams Why's that not related to P vs NP? If you can prove that the problem is in NP, but that the best possible algorithm is exponential in the input (like, $2^n$ operations), doesn't that give you $P\neq NP$? I'm not saying this is what is shown here (which seems not to be the case, since they don't seem to prove that it actually is the best possible algorithm), I'm just speaking theoretically, wouldn't such a proof solve the question?  
> **username_6**: Consider the statement *"The high-degree terms involving products of *x_i* cannot be simplified or linearized without assigning values to *x_i*. Due to the multiplicative and recursive nature of the equations, isolating $x_i $ or expressing them in terms of other variables is not feasible,"* At best, he is assuming a particular kind of algorithm here. At worst, this is handwaving. Either way, it's not a rigorous proof of P $\neq$ NP  
> **username_7**: Note that there are more authors of papers called Ping Wang. I tried to correct somebody on misidentifying the author only to find out that the page that I found had miscontributed the paper to the wrong Ping Wang itself.  
> **username_3**: Also see this: https://scottaaronson.blog/?p=458  

---

## 1 answers

### Answer by username_6 on 2024-12-19. Score: 10 | Accepted answer

The paper contains the statement:

> The high-degree terms involving products of $x\_i$ cannot be simplified or linearized without assigning values to $x\_i$. Due to the multiplicative and recursive nature of the equations, isolating $\_$
> or expressing them in terms of other variables is not feasible,"

This seems to indicate that he is (probably without realizing it) assuming a very particular type of algorithm for solving the problem. Thus, this paper does not contain a proof that P $\neq$ NP, and seems very unlikely to lead to one.


---

