A Solution of the P versus NP Problem?
arxiv.org
arxiv.org
Pros: The author is not a dilettante, and is actively researching in the area (http://theory.cs.uni-bonn.de/blum/Forschung/forsch.var)
Cons: It's not my area, but I was expecting something a little more novel for a solution to P?NP. This almost seems too simple (it might almost fit in a margin...).
Could be pro or con: Single author. It's becoming rare for important new work to not have multiple authors, especially from professional academics. However, Andrew Wiles...
Grigori Perelman also comes to mind.
A plausible proof of "P != NP" won't be quite as simple to express, since it needs to prove that all such algorithms do not run in polynomial time.
Please forgive me if my liberal use of the language is an offense
That sounds hard but, If for any NP-Complete problem there exists no P solution then for all NP problems there is no P solution. So this proof sounds like it has the right shape.
- The proof will turn out to have a flaw
- The flaw will not be that hard to find (though probably not completely trivial; but rather of the kind: it takes much time to go to the details of the proof arguments)
- The flaw will not be interesting in itself and will not advance the field
> ...this guy is an established senior researcher at the University of Bonn
I make more mistakes by 09:00 than most people will make all day. Hell, my girlfriend would suggest that we can move that time forward a couple of hours.
/dodge
As a PhD student in Programming Languages, can I request a reference?* Nobody managed to provide one on MathOverflow, and that's the StackExchange for professional mathematicians:
https://mathoverflow.net/q/226966/36016
Of course, your claim is vacuously true, since you can add a trace of all steps of a proof verifier. It's also vacuously true because you can add a dump of the Internet to the proof. Neither thing is insightful.
> what we normally think of as an "honest proof" is a series of steps each of which follows from the previous by application of one of a finite number of axioms or rules of deduction, and such an "honest" proof is thus checkable in linear time by checking each step
Also, for the record: actual formal proofs for (say) standard ZFC are exponentially bigger than anything you want to work with.
EDIT: To clarify, I didn't mean to imply I'm some authority, just to suggest I'm not so obviously* an idiot. Which was maybe stupid anyway.
[1]: https://en.wikipedia.org/wiki/Method_of_analytic_tableaux
Aaronson on writes very well.
Accusing others of "virtue signaling" is a much clearer example of "virtue signaling" in my opinion, since it's a particular population that tends to do it, and is used primarily to put down those they disagree with and mark them as belonging to a different group rather than to actually make any kind of meaningful point.
Virtue signalling is the conspicuous expression of moral
values done primarily with the intent of enhancing
standing within a social group.
I feel like I'm taking crazy pills here.
Virtue signalling is usually done by people who sincerely believe the values they espouse - but they emphasize or show those values in order to gain or reinforce social status within the group. It usually is done by proclaiming things you hate, rather than things you like.
If the comment adds nothing besides an "I'm with you guys, that's the worst", it's fair to see and describe it as virtue signalling.
And yes, it happens on both sides of the aisle - heard lots of conservatives proclaiming their distaste for Obama over the last decade.
The whole value of the phrase 'virtue signalling' is that it accuses those you disagree with of inauthenticity. If I'm saying a thing I genuinely believe because I genuinely believe it, I'm not virtue signalling. It's only if the reason for saying the thing is to gain social approval that it's 'virtue signalling'. Any assumption that your opponent is doing something for this reason is uncharitable, and kills rational debate. It's essentially an ad hominem attack.
It's also ignoring the fairly detailed entry that Scott posted explaining in his own words why he started talking about Trump in his blog: http://www.scottaaronson.com/blog/?p=2777 when previously he'd avoided the subject.
Maybe it is virtue signalling, or maybe he really did feel as he claimed, that he had a moral responsibility to speak out against Trump. If you assume that it is only 'virtue signalling', you are cutting yourself off from engaging with his points.
But I'm welcome to roll my eyes at it.
You know that was an interesting and useful concept before you guys decided to turn into yet another empty insult to fling at people.
- Written in Word
- Uses techniques just seem too wimpy for the problem at hand.
- Was published in a predatory journal
The "The nice thing about math is that sooner or later the truth comes out" bothers me. The knowlege in Archimedes palimpsest was lost so long the eventually doesn't seem to be much comfort.
So there's your real answer.
I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed.
I might not get too excited over this proof, either, until another member of the TCS community can vouch for it. There have been many serious-looking attempts at PvNP that turn out to have fundamental flaws.
Sigma_2^p != NP as far as I know and after a brief skimming the paper does not mention P != NP.
Edit: the paper does indeed mention P != NP in the form of P != Sigma_2^p => P != Sigma_1^p = NP. Please disregard my comment.
Why? Why should posting a stab at a complicated problem should be considered career-killing?
There are people who point at others' failures to bolster their own image by comparison. And there are people with fragile egos who are eager to see others in a negative way.
It shouldn't be that way, but it sometimes is, so I wouldn't say the career risk is zero. But I'm still glad he's doing it regardless of the outcome.
https://en.wikinews.org/wiki/Researcher_claims_solution_to_P...
https://arxiv.org/find/all/1/all:+AND+Vinay+Deolalikar/0/1/0...
He is still publishing papers. Seems to be doing fine.
If I were a betting man that's actually where I'd put my money because the paper passes by bogometer test (but I am nowhere near qualified to assess whether it's actually correct).
I think you mean "cojones" (which btw is a very rude word in Spanish). A kahuna is a kind of Hawai'ian shaman.
Bollocks, like many slang words, have multiple meanings in different contexts. It can be used as you stated as well, but "What you said is bollocks" and "You have bollocks for saying it" are very different statements.
It could easily cause some painful embarrassment, but hopefully that would pass with time.
Maybe embarrassment similar to that faced by researchers who's results suggested FTL communication, but it turned out to be a bad fiber-optic cable. I didn't follow up but I assume that team is doing OK.
Sometimes the courage of your convictions means trusting the process to get it right when you're sure you're wrong.
https://www.newscientist.com/article/dn21656-leaders-of-cont...
He is a tenured professor in Germany, there is very little that could end his career (essentially refusing to honour his teaching obligations or being convicted of a felony). At worst, this will be immensely embarrassing, but you can't kick professors out just because they make a fool of themselves.
This is important because the Baker-Gill-Solovay theorem already demonstrates that there exist oracles A != B relative to which P^A = NP^A, but P^B != NP^B. This shows that the problem has contradictory relativizations, and hence can't be proven that way. This matters because it's a litmus test against quack proofs.
I don't think this is a problem here; the proof doesn't appear to be doing that.
I wish the author best of luck.
https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum...
Note that the reverse is obviously true: problems that are easy to solve are also easy to verify.
Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the answer 5 and comparing it with your answer. So we can conclude "Problems that are easy to solve are easy to verify" In other words, P ⊆ NP.
_Now is the reverse true? Are problems that are easy to verify also easy to solve?_
Let me give you an example. Let us assume that the question is "Is 1053188576519689 prime?". You come back and tell me, "No it is not prime, it is divisible by 32,452,867".
1) It is easy to verify your solution. I can divide 1053188576519689 by 32,452,867 and verify that it is indeed divisible. 2) It is hard to solve the problem, I have to try out numbers from 2,3,...,sqrt(1053188576519689), which is quite painful. (Or maybe there is as yet undiscovered better algorithm). So it appears that problems that are easy to verify may not be easy to solve. Or it appears that NP ⊆ P is not true. In other words, it appears P != NP (because if P ⊆ NP and NP ⊆ P, P == NP).
NP problems have wide ranging applications in things like cryptography for example. Let us assume I have a hashing technique. It is easy to hash a document, but hard to reconstruct the document from the hash. Then this technique can be used in auctions where you do not trust the auctioneer. You publicly submit the hash of your bid before the deadline. You do not submit your bid itself, because you are afraid that the person handing out the contracts will reveal the number to his brother-in-law who will bid $1 more than you and win the contract. After the deadline is passed, you send your actual bid to the Auctioneer.
Now 1) Everyone can verify that the documents have not been altered (the hashes are posted publicly, each document can be hashed and compared with its publicly posted hash). So it is easy to verify that the documents have not been tampered with after the deadline.
2) Nobody can construct the document from the hash. So it is not easy to solve for the bid document given the hash. So everyone can post the hash publicly with confidence before the deadline.
If P != NP we can have this type of auctions. If P == NP then there is no difference between posting the hash publicly and posting the document publicly.
People have been taking a go at this for many years now. Grapevine says that several large CS departments in many countries have groups of graduate students devoted to solving sub-problems of the entire proof because it is a prestige issue. Extraordinary claims require extraordinary proof and any proof will go through multiple peer reviews.
Perelman's proof of Poincare Conjecture was studied for several months before being declared true (~3 years) and that was considered "fast". https://en.wikipedia.org/wiki/Grigori_Perelman#Perelman.27s_...
Almost everybody in the field knows we're far from an actual proof with current techniques.
https://cs.stackexchange.com/questions/23260/when-is-the-aks...
The clique function takes a bit string representation of a graph with m nodes (one bit for each pair of nodes, 1s where there is an edge between two nodes) and outputs whether the graph has a fully connected subgraph of size s (a clique).
CNF and DNF are conjunctive and disjunctive normal forms, respectively. CNF has the form (x OR (NOT y) OR ... ) AND ((NOT z) OR y OR ... ) AND ..., while DNF has AND and OR exchanged. Any boolean function can be expressed as CNF or DNF, but this might blow up its size exponentially.
The monotone network complexity is the number of binary {AND,OR} gates you need to compute a function. Monotone because increasing the input (setting a bit to 1) never decreases the output. The basic gates have this property, and if you never use NOT the composition has it too. This means that monotone networks can only compute monotone functions. The clique function is monotone, since adding an edge can never destroy an existing clique.
The CNF-DNF-approximators mentioned are a technique for creating a CNF (or DNF) of such a network by introducing a limited amount of errors (hence approximator) at each step. This is done by switching between CNF and DNF at each gate, but discarding parts of the formula that get too large. (I don't really understand how that keeps the error bounded.)
Using the properties of the clique function, it is possible to show that the total number of errors by a limited CNF-approximator must be large, which means that the switching procedure must have been applied many times. This gives a lower bound on the number of gates in any monotone network that computes the clique function, and this bound is exponential.
The paper under discussion attempts to extend this result to non-monotone networks, which can also make use of negation. To do that, it extends the CNF/DNF-switching to also handle negated variables without introducing significantly more errors. (Again, I don't understand how that works.)
Assuming the extension is correct, any bound on the monotone network complexity using CNF-DNF-approximators also holds for the non-monotone network complexity of the given monotone function.
Applying this to the exponential lower bound of the clique function, this means that there is no non-monotone network of a polynomial number of gates that computes it, which implies that there is no polynomial-time Turing machine, which implies P != NP.
This means, first: If P == NP, then all of these problems become easy, and second: if P == NP and we find an algorithm that solves only one of the NP complete problems quickly, then this algorithm can solve all algorithms quickly.
Reversely, if now this paper's proof is correct so P != NP, then there is no algorithm that solves any of these problems quickly.
You can not uniquely reconstruct a document from a hash value. Indeed, for a typical secure hash function, a given hash value maps to an infinite set of inputs. But because secure hashes are one-way functions, finding any of those inputs for a given output requires brute force. This is why the bidding example works - it's so hard to find any input that hashes to a value that even having one of them is reasonable proof that it was the source document.
*Consider a secure 1024-bit hash function. How many 1025-bit inputs map, on average, to each hash value?
Showing the draft to few colleagues to see if they can spot mistakes before 'shaking the world' is probably a good idea.
If he publishes without consulting peers:
If his proof is correct, he gets unending fame, millions in prize money.
If his proof is laughably flawed, he'll promptly be forgotten as one of the 100s who have been wrong before him.
If his proof is correct, he may end up sharing credit, maybe they'll even publish his work quietly under their own name while he's still waiting for feedback. Maybe that is what we are reading now.
If his proof is laughably flawed, then they'll give him his feedback and only his peers, instead of the whole internet will laugh at him for a day, before it's all forgotten.
I should say, theoretically breaking public-key. In reality the problem may remain too hard to brute force even if the P vs NP problem is solved.
This preprint "implies P not equal NP".
Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.
I especially liked this bit:
David Johnson famously once said, For any instance {G = (V, E)} that one could fit into the known universe, one would easily prefer {|V |^{70}} to even constant time, if that constant had to be one of Robertson and Seymour’s.
I was curious so I tracked down this:
Johnson estimated that the hidden constant is “somewhat larger” than 2 ⇑ (2 ⇑ (2 ⇑ (h/2)) + 3), where 2 ⇑ t denotes an exponential tower of t 2s (2 ⇑ 0 = 1 and 2 ⇑ t = 2^2⇑(t−1)) and h is the number of vertices in H.
If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?
It's easier to get people to devote resources to a hard but solvable problem than to one which may not even be solvable.
What does an O(n^10,000) algorithm do? What understandable problem yields a solution that behaves that way?
In another realm of computational mathematics, matrix mjultiplication is cubic, with optimizations that can approach quadratic time with lots of effort. It's conjectured that matrix multiplication can actually be brought arbitrarily close to quadratic time, but at the expense of ever-more-complex algorithms.
It could very well be that the biggest interesting exponent in P is 3 or 4.
For example, when you have an O(n^3) algorithm and want to process 10,000 elements (which are very few in many situations), it will be, as a rough estimate, 1,000,000,000,000 times slower than processing a single element. This will be acceptable only in very specific situations. As a rule of thumb, an exponent of 2 is already unacceptably slow in many practical situations, and at least on the verge of being unacceptable in others.
You're essentially referring to the idea that could be loads of high-order poly-time algorithms, but we ignore them because those algorithms are slow, and therefore we don't use them. So in the space of all useful algorithms, we simply have a very biased sample.
I think the truth is more profound than that. There actually don't exist very many interesting* algorithms in the classes O(n^(k>3)). The real world we live in and model does not feature many interesting problems for which high-order polynomial complexity algorithms are natural solutions.
*Not sure what the right word to use here is...maybe non-trivial? The point I'm going for is to say that obviously we can invent an O(n^5) algorithm by simply nesting our loops five-deep and printing something, but that's a constructed example. I'm looking for algorithms that naturally arise as a solution to some problem.
Donald Knuth believes P = NP.
Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP
We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.
The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum.
What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.
edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version.
I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed:
First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution.
As I said there must be a flaw in the above algorithm but I can't find it.
Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.
I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.
note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.
Here is why I think the algorithm is correct:
At each step the edge that we are considering is either contained in all the optimal solutions or only some of them. If the edge is contained in all the solutions, increasing its weight to infinity would change the optimal solution and we pick that edge in our solution. Otherwise (if the edge is contained in only some of the solutions) increasing the weight would not change the solution because there is another optimal solution that does not contain that edge so we do not pick that edge.
So we can prove this theorem: At every step of the algorithm if an edge is picked, it is contained in all the optimal solutions.
So the algorithm does not pick any extra edges. Now we have to prove that it includes all the necessary edges. But that is easy because each time that we choose not to including an edge, we are sure that there is an optimal solution in the remaining graph so we are never left with a graph with no optimal solution.
I think you assumed that I meant we change the edge weights from infinity back to their original value at each step but that is not what I meant.
I interpreted this as meaning you were selecting the falsifying removals' edges, instead of removing the non-falsifying ones. You've got it.
It's interesting because it mix two interesting topics, that are well known in the popular science forums, but are very technical and most people don't want to read all technical the details of both.
Relevant xkcd: https://xkcd.com/1240/
If someone could prove P=NP but no one could find an algorithm. That would be incredibly funny in some sense. Like a huge joke played on us by the universe.
However, the reason why I chose to single out crypto specifically is because it has the most to lose if that algorithm exists. Our current methods of encryption become unsafe regardless of whether the algorithm is known or not. I don't think you can claim that your encryption is secure if there is an algorithm that can crack it in polynomial time, regardless of whether the algorithm is known or not.
This is 100% true for all practical purposes. But there is an explicit algorithm for NP-complete problems that runs in polynomial time iff P=NP. The Wikipedia page has it written down. https://en.m.wikipedia.org/wiki/P_versus_NP_problem
Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...
However, while P=NP, the algorithm (oracle) resides on the other side of the event horizon. This is called the MAD paradox.
https://nerdynotmad.com/p-equals-np/
The submitted proof will be found to be incorrect.
Let me explain why P=NP probably won't have any impact, since you see a lot of bullshit claiming lots of bad things will happen. The description of complexity classes like P and NP sweep a lot of details under the rug, and those details matter a lot of practical matters.
The more important of these matters is that complexity is based on worst-case running time, not average-case or typical-case. Often times, we can solve most instances of "hard" problems. We can factor most integers, for example--half of them are divisible by 2, and another sixth divisible by 3. If we limit are inputs to factoring products of two primes of roughly equal size, that is difficult. SAT is another example: it may be the canonical NP-complete problem, but many people think nothing of using a SAT solver (or its cousin, the SMT solver) to solve for things like "how do I find an input that can reach this program point." Except if solving that condition requires, say, finding SHA256(x) = binary digits of pi.
This is one of the main cruxes of P?=NP that doesn't come out much: it's not so much that problems are hard or easy, it's that there's this field of problem instances that seem to be intrinsically hard. Indeed, if you look at restricted versions of these NP-complete problems, you'll find that some restrictions still retain NP-complete, but a very slight reduction in those restrictions suddenly admits a very simple, fast, easy solution.
The related notion that you see people sometimes bring up and dismiss is that P and NP hide constants. This objection tends to be dismissed because most people have no familiarity with polynomial-time algorithms with massive constants. But such algorithms do exist, and they tend to crop up in combinatorial-style algorithms. Which, incidentally, is probably what a polynomial algorithm for an NP-complete problem would be.
Let me explain by analogy of a not-so-recently-solved problem that's a weaker but related notion to P?=NP, L?=SL. This question is essentially asking "could you solve every problem that's equivalent to checking for connectivity in an undirected graph using only constant memory" [1]. The answer turns out to be yes. In essence, there is a deterministic string of coin flips deciding your next vertex that will, if followed, eventually guarantee that you will hit every node in the graph that you can reach within a certain amount of time--if your graph has certain properties. And it's possible to transform every graph into one with this property by replacing every node with an expander graph that's only of size 3^2^16 at the smallest. But since the new graph is 3^2^16 * N, that large number is a constant factor that "doesn't matter".
These kinds of constants show up a lot in combinatorial algorithms. All of these algorithms basically have the property that you can solve the input fairly easy if the input has some structure, but to guarantee that the input has that structure, you need to embed it in a very large instance. I argue that, if P=NP were to hold, it would have a similar form to these algorithms. We know that there are some instances that just seem to be intrinsically harder than others, and we know that there are large classes of instances that can be easily solved with fast algorithms. If we haven't been able to generalize the fast algorithms to cover the hard instances but a "fast" (ignoring constants) algorithm must exist, then the apparent complexity has to be generated from sort of fiendish complexity-multiplying, combinatoric structure.
We already see in modern security algorithms that ciphers and hashes have to carefully choose their parameters to make sure they stay in a hard subset of their input algorithms. So even if P=NP, the hard subset is likely to remain much harder than the easy subset, and that gap is sufficient to maintain security.
[1] A very imprecise characterization.
"To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the proof won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: the paper claims to give an exponential circuit lower bound for Andreev’s function, but that function as defined in Section 7 of the paper seems clearly to have a polynomial-size circuit, based on polynomial interpolation (thanks to Luca Trevisan for this observation). So I don’t see how this can possibly stand. Please just stop asking, and if the thing hasn’t been fully refuted by the end of the week, you can come back and tell me I was a closed-minded fool."
None of those papers have been accepted as correct, the problem remains open.
There's a gazillion articles describing the context and importance, and I suggest you do a web search for something like "P vs NP and why it's important".
Here's one: http://www.scottaaronson.com/blog/?p=459
HN discussion: https://news.ycombinator.com/item?id=1605415
A good place to start to get a sense of what's going on with this specific paper is this thread, but more particularly, the articles linked from it. One that I think is a great starting point is this one:
https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum...
But you should perhaps start by asking the question you actually want the answer to - it sounds like you didn't. So take a moment, do some reading, then come back with particular questions. They may already be answered, but before you did the outside reading you didn't realise. That's what happens to me.
This hasn't ever happened.
You can prove an algorithm is in NP-hard by reducing another NP-hard problem to it. You can prove an algorithm is in P by showing the algorithm.
If you find and efficient algorithm to a problem in NP-hard, you show P == NP. No one has ever done this.
P != NP is considered by many to be most likely true.
Thanks for clarifying - I always though that's what the above meant but I didn't realise that the reduction side was also important.
I did some graduate level research on P =? NP, specifically in the SAT space <https://en.wikipedia.org/wiki/Satisfiability>.
In particular, I helped design MARMOSET (Marmoset Automated Reasoner Mostly Only Solves Easy Theorems), a competitive SAT problem solver. <http://www.cs.unb.ca/research-groups/argroup/marmoset/> . (It's a cool name... I didn't come up with it :))
The conclusion I drew was:
1. P != NP because you can convert in polynomial time every SAT problem down to Horn clauses, which are P to solve, plus non-Horn clauses that cannot be converted i.e. have intractable intrinsic NP complexity whose reduction to the polynomial space requires "clairvoyance" of the quantum computation variety.
2. Nobody's really interested in a proof that P != NP.
That said, I only spent a couple years at it, and my memory may be faulty and I might change my mind if I revisited the issue. Part of me has always felt that the Horn clause reduction is a first step to isolating problems for a next step, but again — it's been a long time.
I doubt that.
P!=NP is one of them.
Let me clarify: Nobody appeared to be interested in funding a graduate student to prove P != NP.
That having been said, an accepted proof that P != NP would result in a Turing award and an additional $1M for solving one of the seven Millenium Prizes. This has been an open problem for decades, and it is a problem of enormous importance and visibility.
This is not the case. In my day job I need to worry about what happens if ECDSA is broken. One way that can happen is quantum computation -- but that has a relatively transparent development timeline we can plan for. The other way in which ECDSA could be broken is if P==NP and the discrete log problem can be transformed in polynomial time into another polynomial time algorithm. All of our customer funds could be stolen at that point, with liabilities in the hundreds of millions or billions of dollars.
That's lot of customer money on the line if that happened. My employer might need to pay BIG money for insurance against a P==NP break of ECDSA, or else risk going bankrupt if it happened. A proof of P!=NP would translate directly into cost savings, either in not getting that insurance or in drastically reducing premiums for it.
Now that is some good SAT solver name - keeping user's expectations low, I guess? Nice choice! ;)
There's some interesting ideas in the paper, the researcher has done good work in this area before.
Think about non-constructive proofs.
To me it does not seem that the author of the paper uses weird "coffeinated" non-constructive proof arguments in it.
Also, this very same Facebook link was linked to at https://cstheory.stackexchange.com/questions/38803/is-norber... by https://cstheory.stackexchange.com/users/24/opt
Neither this HN user, that FB user nor that stackexchange user seems like anyone important, respected or relevant in the field of CS of this article (correct me if I'm wrong).
Smells like a bad attempt at karma whoring to me.
I am willing to toss this out of hand...but look at yitang zhang or perelman. who knows? best of luck
dblp is the proper place to check computer scientists' record, not arxiv/google scholar.
However the author missed that there is a special case for N == 1, where actually P == NP (sorry, I could not resist).
P is the union of all TIME complexity classes defined by n^k for every natural k.
NP is the union of all NTIME complexity classes defined by n^k for every natural k.
This is probably why there is not a proof yet, since the truth is undesirable.
Say what? A lot of work is based on the assumption that P!=NP so you have to be clever in other ways.
This is probably why there is not a proof yet, since the truth is undesirable.
P != NP is natural, you just gotta roll with it.
Arguably, P=NP makes CS less fun, since an efficient "universal algorithm" could solve a vast class of problems in polynomial time, while P != NP means there's more room for programmer creativity making intractable problems tractable in special cases.