Jump to content

Talk:P versus NP problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Gao Ming paper

[edit]

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Yes, it is only a pre-print, and he'll have to publish it in a journal, but I've skim read through Gao Ming's paper, and I'm not seeing the problem. I think we should refer to it until such time as anyone finds a flaw in it. My edit was reverted by someone who didn't say why. What do others think? Dan88888 (talk) 16:12, 11 March 2022 (UTC)[reply]

Lots of people publish "solutions" to famous open problems. For reasons of due weight, to include such an announcement in this article would require significant coverage in reliable, secondary sources, rather than a "skim read" by an individual Wikipedia editor. --JBL (talk) 16:47, 11 March 2022 (UTC)[reply]
I agree with JBL. There are hundreds of these crank papers out there. Trying to cover each one would overwhelm our article, and also violate the requirement of WP:FRINGE that we cover fringe material according to what mainstream sources say about it, not what the fringe material says about itself. —David Eppstein (talk) 17:24, 11 March 2022 (UTC)[reply]
But Dan8888 has skimmed it and doesn't see a problem! Why isn't that good enough? Personally I'm convinced N vs NP has now been solved. EEng 19:55, 11 March 2022 (UTC)[reply]
Just set P=1? —David Eppstein (talk) 20:45, 11 March 2022 (UTC)[reply]
I've learned more about Wikipedia this weekend, and now agree with the two comments above (but not with the ones below). Incidentally, my native Chinese speaking friend is convinced Gao Ming is a made-up name, which doesn't bode well for it being a successful attempt! Dan88888 (talk) 17:05, 13 March 2022 (UTC)[reply]
I see it has got as far as being published with a peer review process https://link.springer.com/chapter/10.1007/978-3-031-28073-3_41
https://saiconference.com/FICC2024/CallforPapers Dan88888 (talk) 16:29, 5 February 2024 (UTC)[reply]
Yes sure: [1] [2]. --JBL (talk) 17:33, 5 February 2024 (UTC)[reply]
Hey, I'm not claiming it is a good publisher. I've never heard of it before. However, the evidence you provided I see falls short of proving it is a not a good one.
Also, by way of comparison, the 2010 “proof” was quickly shot down on the internet, and this time, that hasn't happened. I would think, there would be people motivated to move in, particularly on a journal that was perceived as a bad one. ~~~~ Dan88888 (talk) 08:57, 6 February 2024 (UTC)[reply]
No, as a general rule people do not waste time debunking fake proofs published in fake journals, for obvious reasons. --JBL (talk) 18:28, 6 February 2024 (UTC)[reply]
Strong claims require careful checking. Remember Wiles and Fermat's Last Theorem? He did not do a pre-print, but he presented the proof over several days of lectures to a group of other expert mathematicians, and they agreed he had solved it (rather stronger statement than a single person skimming a paper). But even so, a fatal bug was found in the peer review process, that took two years to fix using techniques that were not in the original proof. So we need to let the peer-review process play out. LouScheffer (talk) 04:26, 12 March 2022 (UTC)[reply]
But in the end Wiles was right after all, so all that checking and debugging turned out to be a waste of time. If everyone'd just believed him in the first place ('cause he is, after all, wicked smaht) then they could have spent those two years doing something useful like squaring the circle. EEng 06:06, 12 March 2022 (UTC)[reply]
I disagree. A proof has to be well checked and organized. The fact that two years was spent on rectifying any mistakes only serves to strengthen his claims. Science peer reviews are meant to be critical. If scientists randomly accepted something without thorough analysis, it could lead to entire systems crashing down further down the line. Especially when considering problems as crucial as the Millenium prizes which are considered to have widespread effects across multiple fields and set precedencies, if solved, for entire branching fields with in them. If it isn't subjected to intense scrutiny, the repercussions of post-implementation failures would be massive. Tcwade634 (talk) 20:10, 4 November 2025 (UTC)[reply]
I suggest you take your facetiousness checker in for recalibration. EEng 09:32, 16 March 2026 (UTC)[reply]
It has been published in an engineering journal and the editor is an engineer, not a mathematician, so I don't know how serious was the review. It has received no citation, no debunk nor confirmation, but that could just be a consequence of the paper not looking serious from a distance, making cryptographers reluctant to spending time reviewing it.
About the proof, it looks incomplete. The author tries to prove that any attacker against their cryptosystem is an exponential algorithm. AFAIK this is not the standard way of proving things in cryptography, because it's generally impossible. Maybe the proof requires an hypothesis, that the equation system which is claimed to be equivalent to the cryptosystem, is not solvable in polynomial time. If I'm right, the proof looks circular. If it is not, then it would merit a clearer explanation and a more formal wording, because extraordinary claims require extraordinary proofs. Hypesnave (talk) 09:13, 16 March 2026 (UTC)[reply]
The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Where is the algorithm allowed to run?

[edit]

afaik, the current problem description does not specify 'where' the algorithm is allowed to run. On a turing machine, or just any possible system in the physical world? The latter then means that for P != NP there is no possible physical system what so ever, that can compute NP problem in polynomial time. No time loop computers, nothing.

I think these are slightly different problems because if ANY system is allowed this is really a problem about reality itself, not just turing machines 2A00:20:600D:2768:4635:D54A:452:6124 (talk) 21:54, 23 September 2024 (UTC)[reply]

This article is exclusively about the properties of Turing machines and not real-world computers. See the Physical Church-Turing Thesis for discussion of physically realizable computers. Stellaathena (talk) 16:32, 16 September 2025 (UTC)[reply]

Consequences of solution section

[edit]

This section feels very much like it is ChatGPT written. Sure is has some quotes and citations which is unlike ChatGPT, but the style of writing besides that seems exactly like the style ChatGPT writes in. If someone competent used GPT to help them write an accurate section that's fine, but I'm worried about the possibility of someone just copy pasting GPT's output verbatim and adding some links in. 104.39.200.237 (talk) 15:49, 16 December 2024 (UTC)[reply]

The text in that section is much older than ChatGPT. --JBL (talk) 17:31, 22 December 2024 (UTC)[reply]

Philosophical implications

[edit]

Could someone write a section on the philosophical implications of solving the problem? Countercheck (talk) 00:57, 23 August 2025 (UTC)[reply]

"Vinay Deolilakar" listed at Redirects for discussion

[edit]

The redirect Vinay Deolilakar has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2026 February 8 § Vinay Deolilakar until a consensus is reached. 1234qwer1234qwer4 08:00, 8 February 2026 (UTC)[reply]

P=NP article

[edit]

Hi JayBeeEll: Lede should be a summary of the article and not introduce material which is not first covered in the main body of the article according to WP:Lede. Could the article be brought into the Lede format consistent with MOS as I tried to do yesterday? ErnestKrause (talk) 20:38, 25 March 2026 (UTC)[reply]

Hi ErnestKrause, neither of your edits had any discernable relationship to lead-body coherence that I can see. I would be happy to discuss this in more depth, but may I propose we do it at the article talk-page Talk:P versus NP problem so that other editors of the page will also have the opportunity to weigh in? --JBL (talk) 20:49, 25 March 2026 (UTC)[reply]
I'm not sure how you are substituting a graph for SAT in the Lede section where one normally expects to see a regular Infobox with the conventional information contained in Infoboxes. That's not what the current article is doing; possibly you can explain why MOS is not being followed here. Normally, the lede only summarizes material already presented in the main body; why is it different here? ErnestKrause (talk) 20:53, 25 March 2026 (UTC)[reply]
Infoboxes are a scourge and a waste of reader attention. They do not and often cannot accurately summarize technical topics. The boxes in the lead are not infoboxes, and should not be. They are, specifically, WP:SIDEBARs, and their placement in the top right corner of the article is the standard placement for a sidebar. —David Eppstein (talk) 21:00, 25 March 2026 (UTC)[reply]

Sidebars and Navboxes do occur in many Presidents articles as well, for example, after the Infobox for a President there can be a Navbox about the political party that the President belongs or something akin to that. Here, you are saying that the Infobox should be dropped and a Sidebar which looks alot like an ad for the million dollar Millenium prizes is substituted. That's not what Wikipedia generally defends as its policy for WP:Lede. Still, if you are sysops and are displeased with Lede guidelines then that's your informed viewpoint. Why are Infoboxes from the lede a 'scourge'? I've only brought this up because I'm interested in how quantum computers are covered in Wikipedia in relation to NP complexity (Shor's algorithm implications). This article's Lede section looks atypical for Wikipedia; its hard to see the article moving towards GAN in its current format. ErnestKrause (talk) 21:19, 25 March 2026 (UTC)[reply]

No, I'm not saying the infobox should be dropped. There is no infobox. That is a good thing. It should not be added.
Presidents and concepts in technical mathematics have very different natures that makes the question of whether infoboxes are useful for them have different answers. Infoboxes are a scourge because they present things as isolated and absolute facts, things that can be stated in a single name or date, rather than as things that need to be spelled out in more detail with full sentences and paragraphs. That works for the dates, predecessors, successors, party identification, and running mates of a presidency but not for describing major research questions in mathematics. Anything you might try to nail down to a single piece of information (like what year was it formulated) is likely wrong: the answer is shades of gray, not black and white. —David Eppstein (talk) 21:26, 25 March 2026 (UTC)[reply]
Its very difficult to see this article moving toward GAN in this format; its not even clear that it would make it through peer review without multiple challenges. If you are 'safeguarding' this article from regular enhancements which would improve its format, then it can be left there. But since you have done previous GANs, then its not clear why you are defending the current format as if its ready for moving towards GAN? ErnestKrause (talk) 21:30, 25 March 2026 (UTC)[reply]
ErnestKrause I have tried to match up your comments here with your edits, and I have to say I am still confused. The stuff about infoboxes seems to be a non sequitur; as far as I know this article has never had an infobox, and your edits don't seem to be related to adding one. As for the Shor's algorithm stuff, while it is not directly relevant to P vs NP, I do think that there might be a place for some of this content in the article, but perhaps not where you put it; it seems more relevant to the Comparison of P with "easy" problems section. In any case, though, I can't believe that this detail included or omitted would be a key point for GA consideration. --Trovatore (talk) 00:52, 26 March 2026 (UTC)[reply]
Hi Trovatore; Those were separate things which I'll both cover. First, there is no Infobox in the current article and the graphic image which is there looks misplaced in the lede section; I therefore thought it might look better in the main body and follow WP:Lede which only allows summaries of the main boyd of the article in the lede. David actually likes it the way it is currently. Separately, regarding my interest in Shor's algorithm, then the short version goes something like him saying that he has an NP problem not demonstrably in NP-complete which he has a polynomial time algorithm for on quantum computers. Although he gives this one example, I thought it would be nice to expand the current article to give the class of problems which can convert NP problems (not NP-complete) to P-time algorithms on quantum computers. Back to the lede question, David appears to be unsympathetic to using Infoboxes in math articles, while he does like including illustrations and Sideboxes in the lede. These were two separate things. ErnestKrause (talk) 02:45, 26 March 2026 (UTC)[reply]
For quantum vs non-quantum polynomial, the article you want is BQP, not this one. —David Eppstein (talk) 05:06, 26 March 2026 (UTC)[reply]
The BQP auricle is fairly nice, though something more in this P versus NP article might be nice. This is all that I'm finding in the related article in the parallel discussion currently taking place which states: '"A large-scale quantum computer would be able to efficiently solve NP-complete problems." The class of decision problems that can be efficiently solved (in principle) by a fault-tolerant quantum computer is known as BQP. However, BQP is not believed to contain all of NP, and if it does not, then it cannot contain any NP-complete problem.' This is fairly important material though its not represented here on P versus NP with any useful adequacy. Should the current article at least answer the question of does BQP inform or not inform the current state of the discussion of P versus NP? The current one sentence blip about 'quantum algorithms' seems very short. ErnestKrause (talk) 10:49, 26 March 2026 (UTC)[reply]
I share Trovatore's confusion; there seems to be very little relationship between what you actually did and any explanation you've articulated for it. This seems to be a pattern you are repeating in multiple places (e.g., in this damaging edit you made to Riemann hypothesis, and your edits at NP-completeness). Are you sure that you have sufficient technical understanding to be editing in these areas? A detailed discussion of Shor's algorithm, BQP, or quantum computing more broadly would not be appropriate in this article, as these things have only tangential relevance to the P versus NP problem (the subject of this article). --JBL (talk) 18:10, 26 March 2026 (UTC)[reply]
I do think that a brief mention could be appropriate in the section that discusses whether P is the correct abstraction of "easy" or "feasible". That discussion is strictly speaking not part of the P vs NP question, but given that this is probably the article most non-experts would see first, it is probably reasonable to include it. --Trovatore (talk) 20:07, 26 March 2026 (UTC)[reply]
Yes, sure, just as it makes sense to briefly mention Shor's algorithm in the discussion of where integer factorization lies in the hierarchy; but that's not what this addition was. --JBL (talk) 20:39, 26 March 2026 (UTC)[reply]
Could you try to discuss one article at a time? If you asking about the relevance of BQP on the P versus NP page then the relevance seems appropriate, since Shor gives an algorithm for converting an NP problem into polynomial time on Quantum computers. Why not include it and discuss it in this article? ErnestKrause (talk) 15:47, 27 March 2026 (UTC)[reply]
Shor's algorithm is already discussed in this article, appropriately. Your addition concerning these subjects was not appropriate, as it did not relate to the P versus NP problem (the subject of this article). Trovatore and I seem to agree that other discussion of Shor's algorithm or BQP could potentially be appropriate, but that hypothetical possibility is unrelated to your edit. --JBL (talk) 17:17, 27 March 2026 (UTC)[reply]
Euler diagram for P, NP, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)
Its appropriate to add more on Shor's algorithm as providing insight into the relation between the P versus NP problem and NP-completeness. It you know the material then you can add it in your own words to the article. If you do not know the difference between these terms then you could look it up further on the Wikipedia articles for the main subject. ErnestKrause (talk) 20:39, 27 March 2026 (UTC)[reply]
It does not provide insight into NP-completeness because it has no connection to any NP-complete problem. —David Eppstein (talk) 22:08, 27 March 2026 (UTC)[reply]
The suspected relationship of BQP to other complexity classes (Nielsen, p. 42)
This is the Euler diagram currently in the article which mentions the NP-complete problem. My interest is in the class of problems in NP which can be converted to polynomial time on quantum computers. You appear to be saying that there is no connection with Shor's algorithm unless the right part of the diagram is satisfied. ErnestKrause (talk) 01:19, 28 March 2026 (UTC)[reply]
I don't see how the Euler diagram is relevant to the inclusion of quantum complexity here. It says nothing about quantum complexity. —David Eppstein (talk) 01:24, 28 March 2026 (UTC)[reply]

The Quantum complexity theory article seems to answer that point by giving a supplemental figure which I'm including here; it can be envisioned to overlap the Euler diagram in a useful way with recognition of NP-completeness. ErnestKrause (talk) 01:37, 28 March 2026 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:P_versus_NP_problem&oldid=1356644384"