9 ms·
The 50-year-old P-NP problem that eludes theoretical computer science
- msie 5y ago[dead]
- neonate 5y agohttps://archive.md/lKqA5 https://archive.md/lKqA5 http://web.archive.org/web/20211028004018/https://www.technologyreview.com/2021/10/27/1037123/p-np-theoretical-computer-science/ http://web.archive.org/web/20211028004018/https://www.techno...
- adamnemecek 5y agoP=NP but not on Turing machines.
- zaik 5y agoIf there already is a proof of P-NP which is correct but not yet recognized it can probably be found on this page: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm https://www.win.tue.nl/~gwoegi/P-versus-NP.htm (If you can verify any proof using Isabelle or Coq PM me.)
- sasaf5 5y agoWhenever I end up in this list I always wonder whether all these proofs have been refuted. I assume they must have been, considering the problem is still open. But it would be nice if the author had linked to the refutation of at least a few of them. Edit: I now noticed that a few of them have: 3.[Equal]:... Zhu Daming, Luan Junfeng and M. A. Shaohan (all affiliated with Shandong University, China) refute these claims in their paper "Hardness and methods to solve CLIQUE" (Journal of Computer Science and Technology 16, 2001, pp 388-391).
- zaik 5y ago> I always wonder whether all these proofs have been refuted Sadly, no. I have talked to the author of one of those papers and apparently there is not a lot of motivation to check new proof attempts from the relevant people anymore.
- fjfaase 5y agoIt is probably because the proof is either relativizing, natural or algebrizing. It has been proven that those types of proofs are not going to work. The people who submit these kind of proofs often do not understand that they are never going to work. Why would you, as a serious mathematician that understands this to spend your energy to refute some proof for which you know that it already has been refuted. It is the same why designs of peperpetium mobilium devices are not being refuted.
- bawolff 5y ago> (If you can verify any proof using Isabelle or Coq PM me.) Rofl. Yep, if i write a machine checkable proof of the most famous open problem in all of computer science, that's definitely the first thing i'll do.
- baq 5y agoIf it indeed points to a n^100 algorithm (or p!=np), I’d do it. It’d greatly expedite collecting the Clay’s prize money to have someone recognizable validate the proof ;) If it was n^10, well, likely different story, involving three letter agencies, I’m afraid.
- bryanrasmussen 5y ago>I’d do it. It’d greatly expedite collecting the Clay’s prize money to have someone recognizable validate the proof yeah, but in my case (and presumably the previous commenter's case) I don't know who Zaik on HN is and if they are recognizable in the field. That they asked increases my feeling that it is likely they are recognizable but surely anyone who solves p!=np isn't going to just follow something as irrational as a feeling.
- bawolff 5y agoI mean its still a million dollars, and money makes people do crazy things. I'd, i don't know, figure out some way to cryptographically timestamp a hash of the proof first at least.
- bryanrasmussen 5y agofinally the killer app for the blockchain! Before I release my proof I will of course have to develop my ethereum app to verify origins of mathematical proofs.
- BoorishBears 5y agoor like... tweet the SHA256 of the proof text.
- jhanschoo 5y agoPresumably such a formalization is precluded by easy formalizations of executions of Turing machines; already computer scientists describe Turing machines and their executions in most proofs in extremely informal ways because of their tediousness. It would already be a miracle if we had clear formalizations of proofs of major complexity results regarding Turing machines.
- cevi 5y agoSadly, this page hasn't been updated since 2016. I'd love to see some of the more recent attempts at proofs collected somewhere!
- whatever1 5y agoI have low hopes for P=NP. I really don’t see how you can solve for example the TSP exactly to guaranteed optimality without utilizing all of the useful available information. Approximation approaches show that by discarding information you give up optimality guarantees. There must be something in information theory to help with proving that to construct a solution to an NP hard problem you need at least that much information.
- sova 5y agoInformation and computation ("utilization of information") are not equivalent things. The solution is there, staring us right in the face, it's just our primitive methods of sequential operations on a silicon abacus are incapable of rendering a solution immediately. Infinitely parallellize operations, such as with a "quantum computer" and suddenly what is infeasible in one era becomes quite feasible in another. I don't think it's right to equate information theory and computing, because one is per-se data and its solubles/solutions while the other is step-wise sequential logic to infer some step-wise sequential fact.
- chowells 5y agoI think it's time someone had the talk with you: https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3 Quantum computing doesn't do what you think it does.
- oh_sigh 5y agoNot so coincidentally, Scott is the first person quoted in OP's article, as well as the co-author of that comic.
- thewakalix 5y ago“The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.”
- gorgoiler 5y agoI forget my CS in old age. Am I correct in saying, roughly speaking, that everybody knows that P!=NP but we just can’t prove it? Sort of like Fermat’s Last Theorem: the proof is out there.
- sova 5y agoA mathematician can write an equality without anybody raising an eyebrow, but as soon as someone suggests that we can choose the optimal answer on the first "guess" everyone wants to rekindle the Spanish Inquisition. If we can go from "guess" to "obvious solution" then it stands to reason that P=NP. Of course, this is a debate that likely has no clear path without some stroke of insight, because the axiomatic "truth" that confirms it one way or the other is not reachable by induction alone. There is likely an island of consistent axiomatic logical statements that we must not only wait for someone to reach by happenstance, but to decipher and know what to do with them. According to Fermat, his proof was omitted due to lack of space in the margin. I suppose it's good to let others share in the glory now and again, if on centuries-delay.
- mdoms 5y agoWhat?
- bawolff 5y agoSo what you're saying is: If there exists an algorithm that always guesses correctly then we can solve NP problems? That's just the definition of NP restated. One of the definitions of NP is all the problems that can be solved in polynomial time if at every choice we had a method of always guessing correctly. The question of NP=P is if such a method can actually be implemented in polynomial time on a Turing machine. So yes, you are correct, it stands to reason that if NP=P, then NP=P.
- hnfong 5y agoI don't know whether the GP intends this, but one fun way of understanding the GP's comment is: If you believe really so strongly that P!=NP without actual proof, you're actually just making a guess, and then saying you can make good guesses. But the process of doing so implies you actually believe P=NP.
- lincpa 5y agoIt's the most fundamental and core theory of computer science that "The Grand Unified Programming Theory: The Pure Function Pipeline Data Flow with Principle-based Warehouse/Workshop Model" My theory based on the simple, classic, vivid, and widely used in social production practice, elementary school mathematics "water input/output of the pool" as a mathematical prototype, Therefore, it is scientific. The "von Neumann architecture" and "programming paradigms" used by computers now has no mathematical model support. So it cannot prove its scientificity. My theory rebuilt the theoretical foundation of the IT industry, The IT industry is fundamentally associated with mathematics. Solved the most fundamental and core major problems in the IT industry. Therefore, my "warehouse/workshop model" will surely replace the "von Neumann architecture" and other "programming paradigms", become the first architecture in the computer field, and it is the first architecture to achieve a unified software and hardware. Software and hardware are factories that manufacture data, so they have the same "warehouse/workshop model" and management methods as the manufacturing industry. In the IT field, only it and binary system fully comply with these 5 aesthetics: Simplicity, Unity, order, symmetry and definiteness. It has a wide range of applications, from SOC to supercomputer, from software to hardware, from stand-alone to network, from application layer to system layer, from single thread to distributed, from general programming to explainable AI, from manufacturing industry to IT industry, from energy to finance, from the missile's "Fire-and-Forget" technology to Boeing aircraft pulse production line technology, from myth to Transformers. Link: [The Grand Unified Programming Theory: The Pure Function Pipeline Data Flow with Principle-based Warehouse/Workshop Model](https://github.com/linpengcheng/PurefunctionPipelineDataflow https://github.com/linpengcheng/PurefunctionPipelineDataflow)
- enriquto 5y ago> P is big. You just won't believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think a cubic time algorithm is very slow, but that's just peanuts to P. I hate that P is often understood as "easily solvable". There's problems inside P that require O(n^A) time algorithms, where A is some scaringly large ackerman number. And that just barely scratches the surface of P. There are other, unimaginably harder, problems in P. It is very arrogant for us to say that P<NP, when we still know so little about P. I'm rooting for P=NP, even if this only serves to explore harder problems inside P, with terrifyingly slow algorithms.
- baq 5y agoEasily solvable in the context of all other problems being harder ;)
- archibaldJ 5y agoAnd don’t get me started in PSPACE There are so much we don’t know about how space & time complexities commune The weird thing is that GPT3 Codex can perhaps be used to solve some (space-constrainted) subsets of problems that are combinatorial weird. Maybe by pouring all these training data to it it is approximating some unimaginable algo in P that we have no knowledge about Will be wild if there is some (time-space) correspondence; NPSPACE = PSPACE Implies NP = P would be interesting
- IndySun 5y agoRelated. https://rjlipton.wpcomstaging.com/ https://rjlipton.wpcomstaging.com/ https://www.bbc.co.uk/programmes/b06mtms8 https://www.bbc.co.uk/programmes/b06mtms8
- graycat 5y agoThe OP has: > The million-dollar question posed by P vs. NP is this: Are these two classes of problems one and the same? Which is to say, could the problems that seem so difficult in fact be solved with an algorithm in a reasonable amount of time, if only the right, devilishly fast algorithm could be found? If so, many hard problems are suddenly solvable. And their algorithmic solutions could bring about societal changes of utopian proportions—in medicine and engineering and economics, biology and ecology, neuroscience and social science, industry, the arts, even politics and beyond. Okay, I'd like to have a list of such problems! Yes, some of them are 'intractable', but not all. But we are not attacking the problems that are solvable easily enough now and that would "bring about societal changes of utopian proportions—in medicine and engineering". We are not solving such problems because too few of them exist, that is, mostly the problems don't exist. Here's what we can do now and have been able to do easily enough for decades: The challenge of P versus NP is for (1) exactly optimal (for optimization problems) solutions to (2) worst case problems in (3) polynomial time. But if we will settle for 99+% of the savings of optimal solutions for problems that are not worst case but still constitute nearly all the practical problems in reality, then usually we can do well. E.g., 0-1 integer linear programming problems are in NP-complete. The last such problem I attacked had 40,000 constraints and 600,000 variables. I found a feasible solution within 0.025% of optimality in 900 seconds on a single processor computer using ordinary linear programming and some non-linear duality theory. Blunt, practical fact: In practice, there just are not many practical NP complete optimization problems that people want solved. For practical NP-complete optimization problems, we can usually do well, save nearly all the money to be saved with an optimal solution, for reasonable effort, but, in practice, we don't do that very often because there are not many people with such problems who want such solutions -- for the savings, they just don't care enough even to pick up a phone. The claim that an algorithm that shows that P = NP would "bring about societal changes of utopian proportions—in medicine and engineering ..." is just not true -- the economy does not have many such problems. If the problems were there, then people would be successfully attacking those problems now; the "utopian proportions" would create some recruiting. But the recruiting is not there. Over decades sending many hundreds of resume copies showing such problem solving abilities yields no responses. A person good at such optimization faces deep and profound unemployment -- they just CANNOT be hired, at any price, are just NOT wanted. Quite literally, they would have a better career, e.g., make more money, with a simple, ordinary grass mowing service -- no joke or exaggeration. For the problem with 40,000 constraints and 600,000 variables, I got that via email from two guys, a CEO and his buddy. The buddy had tried simulated annealing, run for days, and quit without knowing how close the results were to optimality. Getting the problem via email, in two weeks I did the non-linear duality derivations and wrote and ran the software, for free. Via email I sent the news of success back to the CEO. He was totally not interested: My success would have embarrassed his buddy, and that meant that my work was not wanted, even for $1. Blunt fact: Not many people have any interest at all, and of those nearly all have very little interest. Point: The claim "bring about societal changes of utopian proportions—in medicine and engineering ..." is nonsense because the needed people with the problems are far too few.