Can Amateurs Solve P=NP?
What is an amateur mathematician, what have they done, and what might they do?
Srinivasa Ramanujan was one of the most remarkable mathematicians of the last century. He discovered countless beautiful theorems in both analysis and number theory. With almost no formal training, he was able to discover results that other mathematicians found amazing, even magical. Sadly he died at the age of 32; one wonders what further great things he could have discovered if he had lived longer.
Today I want to talk about the role that formal training plays in solving open problems in mathematics. When people discuss open problems, sometimes the P=NP question is raised as one that might be solved by an amateur. Is this realistic or not?
I have a read Keith Devlin’s book “The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time”—of course the count is now six thanks to the brilliant of Grigori Perelman. I recommend it to you, with the proviso that I could only follow the chapters on the Riemann Hypothesis and the P=NP question. The others on the Hodge Conjecture, the Yang—Mills existence and mass gap, the Navier—Stokes existence and smoothness, and the Birch and Swinnerton—Dyer conjecture, were very hard for me to follow. I do not think this is Delvin’s fault—he is an outstanding science writer—I think it is an inherent feature. Problems such as the Hodge Conjecture require, even to just understand their statement, quite a bit of technical background.
In his third chapter, on the P=NP question, Devlin states that perhaps this problem is one that could be solved by an amateur. I have heard this claim before, and I have mixed feelings about it. Of course we cannot predict who will solve any open problem, and that includes the Millennium problems as well as all other open problems. My mixed feeling comes from saying P=NP could be solved by an amateur seems to mean it is “easier” than the other problems. I do not think this is the case, but ranking the difficulty of open problems is probably impossible.
Let’s take a look at what amateur mathematicians have done in the past, and what they might be able to do in the future on these and other open problems.
Who Is An Amateur?
I think that one of key issues is: who is an amateur? Is an amateur someone who is a completely untrained in mathematics, or is an amateur someone who is not an expert in a particular area of mathematics? According to the dictionary, amateur is from the old French and means “lover of.” Thus amateurs often work on problems without any formal reward or pay. Curiously Perelman was essentially working for “free” when he solved the Poincaré Conjecture, but I think no one would consider him an amateur.
Was Ramanujan an amateur? He was basically self taught, yet capable of discovering formulas that amazed even Godfrey Hardy. For example,
was one identity that greatly impressed Hardy.
Ramanujan shared one trait with many amateurs: his “proofs” were often nonstandard and difficult to follow. This is perhaps one of the hardest issues for an amateur mathematician to overcome—the formally trained world of mathematics has certain rules and styles of how to present mathematics. An amateur may use nonstandard notation, may create new definitions for existing concepts, and may re-prove basic facts. For example, Ramanujan’s first published paper was on some new properties of Bernoulli numbers. The journal editor, Narayana Iyengar, noted:
Mr. Ramanujan’s methods were so terse and novel and his presentation so lacking in clearness and precision, that the ordinary [mathematical reader], unaccustomed to such intellectual gymnastics, could hardly follow him.
Some Results of Amateurs
Here is a partial list of some of the results obtained by amateur mathematicians. Some had no formal training, while others had training but worked on mathematics only as a “hobby.”
![\displaystyle \mathsf{Pr}[A|B] = \mathsf{Pr}[B|A] \cdot \frac{\mathsf{Pr}[A]}{\mathsf{Pr}[B]}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathsf%7BPr%7D%5BA%7CB%5D+%3D+%5Cmathsf%7BPr%7D%5BB%7CA%5D+%5Ccdot+%5Cfrac%7B%5Cmathsf%7BPr%7D%5BA%5D%7D%7B%5Cmathsf%7BPr%7D%5BB%5D%7D.&bg=ffffff&fg=000000&s=0&c=20201002)
This formula is the basis of Bayesian analysis. Most of the credit—although not the name—of the consequences of this formula go to others. Quoting Wikipedia:
Bayes was a minor figure in the history of science, who had little or no impact on the early development of statistics; it was the French mathematician Pierre-Simon Laplace who pioneered and popularized what is now called Bayesian probability.
This comment seems a bit harsh to me. I agree more with Bill Bryson’s opinions about its foundational nature expressed here and in the new book Seeing Further of which he is the editor.
Problem Statements
In order for anyone, amateur or not, to be able to solve an open problem they must understand the problem statement. This is almost silly to state, but it is important. It is hard to hit a fuzzy target. One of reasons some think that P=NP is more approachable than many other open problems is that an amateur is more likely to be able to state P=NP correctly, than many other conjectures.
This is the reason so many amateurs have worked on the Four Color Theorem, the P=NP question, Fermat’s Last Theorem, and Graph Isomorphism: they have relatively simple statements. A simple statement does not mean that a problem is easy, but it does mean that anyone can start thinking about it.
An interesting question is which problems have simple statements?
Can Amateurs Help?
Can amateurs help make progress on modern problems? I think that it is possible. Their lack of fear, the ability of thinking out-of-the-box, the ability to think against the conventional wisdom, all make it possible for them to contribute to science. One of the reasons the pros usually get the credit is that amateurs often do not write their work up properly. They often write papers that have errors, and once we see an error we stop reading and skip the rest—Heegner is a prefect example.
It may be useful to look at the type of contributions amateurs have made in the past.
This suggests there are several ways amateurs can help advance our understanding.
Open Problems
What do you think? Is P=NP the problem most or least likely to be solved by an amateur? Can amateurs still make contributions to mathematics and complexity theory?
A related question: are there relatively simple statements of all the Millennium problems? Such a statement would not necessarily advance their solution, but I would find it interesting if they could be made more accessible. Even experts might be helped by short equivalent statements.
Trackbacks
- Can Amateurs Solve P=NP? « Gödel's Lost Letter and P=NP
- Poincare Conjecture
- World Wide News Flash
- Playing Head-To-Head Texas hold’em « Gödel’s Lost Letter and P=NP
- Proving A Proof Is A Proof « Gödel’s Lost Letter and P=NP
- A New Million Dollar Prize? « Gödel’s Lost Letter and P=NP
- Hedy Lamarr the Inventor « Gödel’s Lost Letter and P=NP
- கேள்வியின் நாயகனே… « ப்ளீஸ், ஒரு நிமிஷம் வெயிட் பண்ணுங்க…
- El matemático Jorma Jormakka proclama haber resuelto cinco problemas del milenio « Francis (th)E mule Science's News
- Thanks For Sharing « Gödel’s Lost Letter and P=NP
- In Praise Of P=NP Proofs | Gödel's Lost Letter and P=NP
Maybe there is some way to hook up amateurs who think they have something of interest with patient experts. That way, the expert could help them rephrase their work in a more conventional way.
I would imagine that this could be frustrating for experts who are frequently contacted by cranks, but maybe there is some way to help mitigate the amount of crankiness for all involved.
Gilbert,
I like this idea. I do think some system like this could work.
Maybe some well structured society of amateur mathematicians/scientists can elect candidates to be considered by professionals? There would still be the problem of not creating a society of cranks that promote cranky “proofs” as a group, because such a turn of events can be truly painful.
I am an amateur mathematician with a graduate education in mathematics. I am also a professional actuary. I have written up two arguments that P != NP. One was published in the journal Progress in Physics. They both can be found here:
http://arxiv.org/abs/cs/0607093
http://arxiv.org/abs/cs.CC/0507008
In my mind, the P vs. NP problem is settled. However, the arguments in my papers have failed to convince the majority of mathematicians and computer scientists. I understand why, as I have corresponded through email with a complexity theorist at my alma mater: The reason is that they believe that my arguments do not cover all possible algorithms and are limited to only certain types of algorithms. I disagree with this and can explain why.
Almost all of the contact that I have had with the computer science and mathematics community has been over the web, through email and comp.theory and sci.math. While the web has its merits, I would really like to talk with a professional mathematician or computer scientist who is an expert in complexity theory over the phone (or in person if possible). Personal contact always makes things better. The web can be very impersonal and sometimes nasty. Maybe an expert could help me write down my arguments in a manner that would be more convincing to the expert complexity theorist. Anyone interested may email me at cafeinst@msn.com. Thank you.
http://blog.computationalcomplexity.org/2010/05/structure-or-lack-thereof-of-data.html
Additionally, your bounds of O(sqrt(2^n)) being the best you can do are obviously wrong, as they contradict known algorithms which run faster. In fact, Lipton (semi-)recently did a post covering some new work.
http://rjlipton.wordpress.com/2010/02/05/a-2010-algorithm-for-the-knapsack-problem/
Ross Snyder said: “Additionally, your bounds of O(sqrt(2^n)) being the best you can do are obviously wrong, as they contradict known algorithms which run faster. In fact, Lipton (semi-)recently did a post covering some new work.
http://rjlipton.wordpress.com/2010/02/05/a-2010-algorithm-for-the-knapsack-problem/”
If one reads Lipton’s post, one sees that this 2010-algorithm for the knapsack problem does not solve all instances of the SUBSET-SUM problem because it cannot output “no solution”.
There are still no known algorithms which solve all instances of the SUBSET-SUM problem that beat the $2^{n/2}$ time. And there never will be any.
Craig, I aint no specialist, but there is no necessity to output “no solution”.
https://stellar.mit.edu/S/course/6/sp08/6.080/courseMaterial/topics/topic1/lectureNotes/lec9/lec9.pdf
In case you’re not convinced: once you have an algorithm that find a “yes” in O(2^0.311n) time, then you can create a new algorithm with the following behavior:
-ouput “yes” if the old algorithm does
-output “no” when no “yes” is found in time more than O(2^0.311n).
Then you have an algorithm that both output “yes” and “no” in time O(2^0.311n).
That beats your O(2^0.5n), meaning that either the algorithm for the knapsack problem is false, or your proof .
Personne,
The algorithm in that paper does not always successfully find a “yes” answer when there is a “yes” answer, so what you are proposing can’t work all of the time. If you don’t believe me, read the comments to Lipton’s February 5, 2010 post. One of the authors admits this.
There is still no deterministic and exact algorithm which beats O(2^{n/2}) time and solves all instances of SUBSET-SUM.
I did Craig, and no I don’t read that. Let’s try something else: do you agree that 1) clique is a NP-complete problem solvable in less than O(2^n/4)?
http://en.wikipedia.org/wiki/Clique_problem
http://www.labri.fr/perso/robson/mis/techrep.html
and 2) that Cook-Levin theorem guarantees the existence of a polynomial time reduction from subset-sum to clique?
http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
Then, you have to conclude that an algorithm exists which solves subset-sum in time O(2^n/4) up to a polynomial factor -even if you don’t happen to know this algorithm.
Do you see it now?
Craig (if I may—we’ve interacted once before on another blog),
The responders are basically right, even if the details are deficient. Your last statement “There is still no deterministic and exact algorithm which beats O(2^{n/2}) time and solves all instances of SUBSET-SUM.” may be true, but is revealingly besides your point—insofar as you claim to have proved there is no such algorithm.
The overall point is, how do you know the “Meet-in-the-Middle” algorithm gives the best possible time for Subset-Sum? For instance, what have you done to show that its clever idea cannot be used over and over again, recursively?
A lot of people would agree with your belief, especially if you weaken it a little to assert that Subset-Sum requires time at least some fixed root of 2^n, or what is the same thing, order 2^{cn} for some constant c > 0 (possibly ignoring lower-order factors). Since the standard reduction from 3SAT to Subset-Sum runs in basically linear time, this aligns with the belief called the “Exponential Time Hypothesis” (ETH). However, being right in the light of Nature is not the same as possessing a proof.
Let me give an example, due to Leslie Valiant, of algorithms being able to do things that “normal” human reasoning would not expect. Consider Boolean formulas C_1 & C_2 & … & C_m where each clause C_j has two un-negated variables, such that each variable occurs in at most two clauses, and the graph formed by the m+n clauses and variables is planar. To wit, the graph has an edge (x_i,C_j) if variable x_i occurs in clause C_j, and the graph also has a cycle on the variables, (x_2,x_2),(x_2,x_3),…,(x_n,x_1). Such a formula is obviously satisfied by the “all-true” assignment, but the question is, how many other assignments satisfy it?
That problem is #P-complete, hence NP-hard. Most interesting, the problem remains NP-hard under “randomized” polynomial-time reductions, if you only wish to determine whether the # of satisfying assignments is even or odd. Ditto for computing the number of solutions modulo 3, or 4, or 5, or 6…
Now suppose you wish to compute the # of solutions modulo 7. By the same logic as for modulo-2 being (randomized) NP-hard, you’d expect this to be equally hard. After all, there is nothing about the statement of the problem that suggests a particular role for “7”. Nevertheless, there is a genuinely efficient polynomial-time algorithm to compute this! The details are all in Valiant’s paper, and the distinguishing feature of “7” was subsequently isolated in papers by Jin-Yi Cai and his students.
“There are many more things in heaven and earth than are dreamed of in your philosophy”—and yet a proof of P != NP must rule all of them out. Short of such a proof, one is imposing presumptive limits on Nature. For a more-accessible example of a non-obvious poly-time algorithm, try designing one for the language {(N,x) : N is a nondeterministic pushdown automaton that accepts x}. This is the “universal problem” for context-free languages. All texts I know content themselves with showing that every individual CFL belongs to P, which is what you get if you fix an N rather than let it be a variable part of the input. Those texts build on converting an NPDA N into a context-free grammar G and then converting G into Chomsky normal form, but present the latter process with an exponential blowup in the nullstring-elimination step. You might think this kind of nondeterminism allows nothing better, but in fact by representing nullable variables as “BNF [option]s” and using a list construction, one can do it! I don’t know of any source that has a whole proof of this, so writing it nicely would be a real mitzvah!
Or let’s put it this way. According to your paper, the best we can ever hope to do on the sorting problem is O(sqrt(n!)) which is obviously incorrect. Why can we solve the sorting problem in time O(nlogn)? Where have you shown that Subset Sum can’t be solved in a similar way to the sorting problem?
Basically this reduced to asking how you know the objective function for minimization is in the form P + T? What if for every ‘virtual processor’ you make you double the amount of processing that can be done? What if you can trade space for time for processors? 3S + 4T+ 5P might be an objective function to minimize. It seems like there are some explicit assumptions in your ‘cost minimization argument.’ Namely, you assume that every ‘file’ in the ‘filing cabinet’ must be checked. But like the sorting problem, this might not be true! This is essentially what the P = NP question is asking!
I will respond to Kenneth W. Regan, as his comment is the most representative of the general opposition to my arguments. I’d like to respond to the other comments but my time is limited now. I’m going on vacation tomorrow. Maybe I’ll have time later this week.
Notice that Ken’s opposition to my argument is a philosophical opposition. His argument is essentially “How do you know someone clever will not come up with a way that you have not considered in your proof and beat the Meet-in-the-Middle algorithm?”
But consider that I could pick any proof of any famous theorem and use a similar argument to refute that proof: Let’s pick the Fermat’s Last Theorem proof by Wiles and Taylor (which I’ll admit is above my pay grade). I can refute this proof easily (even though I don’t understand it) by saying the following:
That proof is at least partially based on the Zermelo Fraenkel axioms. Godel’s 2nd Incompleteness Theorem says that it is impossible to prove (without making questionable assumptions) that the ZF axioms are consistent. Hence, it is conceivable that the axioms that Wiles and Taylor used to prove FLT are inconsistent, which would invalidate their proof. Hence, their proof is invalid.
My point is that there is no proof that is 100% right. You can always give a valid logical counter-argument which says “maybe your proof is wrong.”
Yes, I’ll admit that it is conceivable that there is some algorithm which works in a way that nobody has ever dreamed of before that beats the running-time of the Meet-in-the-Middle algorithm. There are certainly lots of clever algorithms out there which do things that nobody has ever dreamed of before. But is such an algorithm plausible? No, as I have demonstrated in my papers.
In the first paper I have written, “Complexity Science for Simpletons”, I showed that the SUBSET-SUM problem with a set of cardinality n is equivalent to taking the “or” operator of two SUBSET-SUM sub-problems with sets of cardinality n-1. While the sets of cardinality n-1 are the same in both sub-problems, the target integers in both of these sub-problems are different. Hence, in order to take the “or” operator of the two sub-problems, it is necessary to solve both of them (unless the first one solved has a solution.) [This is common sense, just as it is common sense that if one picks two different people and wants to know whether at least one of the two people has red hair, one must examine the hair of both people (unless the first person examined has red hair.)] With this assumption, I show in my paper that the Meet-in-the-Middle algorithm has the fastest running-time of all algorithms which solve SUBSET-SUM. Is it possible that an algorithm exists which beats this running-time? Yes, but such an algorithm would have to work by magic, since it would essentially be able to always tell whether at least one of two people has red hair without examining the hair of both people.
In the second paper I have written, “A new and elegant argument that P!=NP”, I showed that in order for an algorithm to beat the Meet-in-the-Middle algorithm and deterministically solve the SUBSET-SUM problem, that algorithm must do so without searching the 2^n possible solutions – such an algorithm would have to find the solution by magic. (It would have to make use of an oracle.) Can this type of algorithm exist? Yes, if magic exists. But is such an algorithm plausible? No, as it is generally accepted that there are no magic algorithms, just as it is accepted that the ZF axioms are consistent.
While I don’t know if I have convinced anyone that my arguments are valid, I hope I have made people think about the P vs. NP problem in ways that they haven’t thought before. I’ve been thinking about the P vs. NP problem for 20 years now since I had first heard of it, and essentially even before I first had heard of it when I started to question why it is easy to learn from a book how to solve a Rubik’s Cube but much more difficult to write such a book.
Craig, you are asserting that any algorithm trying to solve an NP-Complete problem must examine all 2^n possibilities. This is an assumption you make in your framework. An axiom, if you will. So far in conversation you’ve sort of been stating this assumption explicitly. More importantly, you’ve also encoded the assumption implicitly within your framework. Then you derive from this assumption that any algorithm must take exponential time. Duh, tautology. Essentially you assume something that may as well be P != NP and derive P != NP. The real question being asked by P ?= NP is “do all exponentially growing number of paths in this Turing Machine need to be examined to know if there is a satisfying path of polynomial length?” Again, your “proofs” assume yes and then “derive” P != NP. What we want is a proof, a real proof, that all (well, an exponential number of) paths must be examined (in the worst case) to answer the question. This you have not provided.
The question of the sorting problem still stands. Given your Meet-in-the-middle framework, why are we able to solve the sorting problem in much less than O(sqrt(n!)) time?
Also, you may want to consider taking this conversation out of comment-section band. If you would like I can email you at the email address you’ve provided. Have a safe and fun vacation.
I just got back from vacation. I’ll respond to Ross Snider:
He said: “According to your paper, the best we can ever hope to do on the sorting problem is O(sqrt(n!)) which is obviously incorrect. Why can we solve the sorting problem in time O(nlogn)?”
Actually, this is not true. The argument in my paper is about the SUBSET-SUM problem, not about sorting (although the Meet-in-the-Middle algorithm requires sorting).
According to the language of my paper, we would say that since we have a lower bound of Omega(n log n) for solving the sorting problem, an upper bound for the number of “imaginary processors” for this problem is O(n!/(n log n)), since the solution space of this problem has size n!.
He also said: “Craig, you are asserting that any algorithm trying to solve an NP-Complete problem must examine all 2^n possibilities. This is an assumption you make in your framework. An axiom, if you will. So far in conversation you’ve sort of been stating this assumption explicitly. More importantly, you’ve also encoded the assumption implicitly within your framework. Then you derive from this assumption that any algorithm must take exponential time. Duh, tautology. Essentially you assume something that may as well be P != NP and derive P != NP.”
When I said the algorithm for SUBSET-SUM must examine all 2^n possibilities, I did not mean that it is necessary for the algorithm to take 2^n time, as it is possible for the algorithm to examine many possibilities at the same time, just as the Meet-in-the-Middle algorithm does. I never assume that an algorithm for solving SUBSET-SUM must take exponential time.
Ross, please feel free to email me, if you want to have this conversation outside of this blog.
In consideration of your comments, I have updated my paper http://arxiv.org/abs/cs/0607093 with lemmas and proofs.
Your “proof” of the inductive hypothesis by contradiction in Lemma 1 is invalid. You say: “if
, this algorithm would be able to automatically determine whether 
without searching set 
for a subset-sum that matches the target integer 
.” This is not a contradiction of what you’ve assumed.
You assumed: “Suppose there is a deterministic and exact algorithm that determines whether
or 
without [exhaustively] searching the set of subset-sums of 
for one that matches 
.” Set 
is a proper subset of 
, and therefore “if 
,” you don’t have to exhaustively search the subset-sums of 
, only the subset-sums of 
. If it was continued ad nauseum, you could solve subset-sum in linear time, so you must consider both cases.
Any valid proof of this sort must prove that the algorithm must search both cases
and 
separately, which is not necessarily true, and in fact may be trivially false in the case of the Meet-in-the-Middle algorithm, since it does not take 
time.
Neil,
I don’t understand your comment “you don’t have to exhaustively search the subset-sums of \{a_1, …, a_{k+1}\}, only the subset-sums of S. If it was continued ad nauseum, you could solve subset-sum in linear time, so you must consider both cases.”
As for the comment, “Any valid proof of this sort must prove that the algorithm must search both cases b−a_{k+1} \in S and b\in S separately, which is not necessarily true, and in fact may be trivially false in the case of the Meet-in-the-Middle algorithm, since it does not take \Omega(2^n) time.”
you are misunderstanding what I meant when I said “search”. I didn’t mean that the search must take Omega(2^n) time, one subset-sum at a time. Read the rest of the paper and you’ll see this. It is clearly possible to search more than one element of the search-space at a time, as is the case with the meet-in-the-middle algorithm.
Neil,
Now I think I understand what you are saying. You are saying that because I am assuming that $b-a_{k+1} \notin S$, the algorithm does not have to search all the subset-sums of $\{a_1,…,a_{k+1}\}$ to solve SUBSET-SUM, only those subset-sums in $S$. That is correct.
However, your conclusion that I did not contradict what I assumed is invalid. I assumed that there is an algorithm that solves SUBSET-SUM without exhaustively searching. It is clear that if one uses this algorithm to solve SUBSET-SUM for n=k+1 and we somehow know ahead of time that $b-a_{k+1} \notin S$, then the algorithm would answer “yes” if $b \in S$ and “no” if $b \notin S$. Hence, the algorithm would solve SUBSET-SUM for us for n=k without exhaustively searching the set of subset-sums of $\{a_1,…,a_{k+1}\}$ and hence without exhaustively searching the set $S$. This is a contradiction. The fact that we know ahead of time that $b-a_{k+1} \notin S$ does not take away from it being a contradiction.
Please email me if you have any more questions.
Neil,
I realized from your comments that I had to do a better communication job with my paper. So I put up a fourth version of it, hopefully the last, up on arxiv.org. Thank you.
That is a great idea, Gilbert. I wonder, though, whether that’s what peer-reviewed journals are *supposed* to do in an ideal world. Would a respected journal spend its reviewers’ time correcting amateurs, even if they’re onto a novel approach? Then there’s the question of intellectual honesty, where even the best experts can be susceptible to temptations…
If you do end up establishing an amateur-meets-expert forum, I’d be very interested to see it (as a spectator more than anything).
A journal referee would not do such a thing. If they see that the author does not understand and makes mistakes, provided that they are not minor, he will propose the manuscript to be rejected. If the manuscript tries to solve a famous problem, errors or lack of precision will not be tolerated. As there is no such a kind board in existence, a proof attempt must be very simple, use only elementary mathematics, make it so clear that it cannot be denied, and use correct mathematical terms. If you do not have the background for it, ask some friendly mathematician. He will not agree that you solved the problem but he may agree to look at the form.
I could imagine an amateur finding a PTIME algorithm for an NP-Complete problem (if P = NP). This of course would entail a constructive proof. On the other hand, it’s a lot harder for me to imagine an amateur proving in the negative direction (if P != NP). The difference, to me, is the separation between the existential and universal quantifier. A clever, brilliant or lucky amateur might uncover a polytime lynchpin algorithm which solves the problem (if such an algorithm exists). To prove that no such algorithm exists is a universal claim. It requires knowledge of some universal claims across all algorithms.
I would definitely leave open the possibility of an expert from another field resolving the question.
There’s no reason to think a negative proof would be harder for an amateur than a positive one. A constructive proof that P != NP would simply involve showing that the assumption of P = NP leads to a contradiction. I like to think Gödel’s Incompleteness Theorem could have been discovered by a very clever armchair mathematician.
What about the reason that Ross gave?
BPP=?BQP could also, in the positive case, potentially be solved by a clever programmer with little math, considering that there are many universal sets of quantum gates and some seemingly very strange restrictions (e.g. limiting use of the SWAP gate) are all that seem to separate the classes right now.
P=?BPP might also be doable by a non-specialist in the positive case.
Claude Shannon is perhaps a near-example of an “amateur” whose information theory made “universal claims across all algorithms”, specifically across all possible encoding and decoding algorithms.
Nowadays we think of Shannon as a mathematician, but in the years leading up to 1948-9 his colleagues regarded him as a working engineer, and not too many people expected to find in the Bell Systems Technical Journal mathematical results as universal as Shannon’s two articles “A mathematical theory of communication” (1948) and “Communication in the presence of noise” (1949).
Even to some of the most eminent mathematicians of the era, it was not immediately evident that Shannon’s two articles were mathematically valid; for example J. L. Doob’s AMS review of 1949 (MR0026286) concluded “The discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author’s mathematical intentions are honorable.”
Perhaps this slow appreciation partly arose because Shannon’s articles described “a method for representing any communication system geometrically” in an era in which information was generally associated to symbols, languages, and algebras.
Well, while i don’t claim to understand this proof:
http://wwwmath.uni-muenster.de/logik/Personen/rds/pnenp.pdf
It doesn’t seem that hard to prove P not equal NP on infinite time turing machines.
Wouldn’t it be enough if an amateur would find a connection from the classical P/NP Problem to the infinite time P/NP Problem ?
———————————————————————————————————–
For example:
1)Define an infinite Sat-Problem much like the classical Sat problem, but with infinitley many variables. You can still check a solution in countably infinitley many steps.
2)Try to find an analouge of Cooks theorem by modeling an infinite non determenistic turing machine with an infinte Sat-Formula.
3)This would imply infinite Sat is NP complete, and can not be solved on an infinite time determenistic turing machine.
4)Define something like an infinite extension of an NP Problem.
Where infinite-Sat is the extension of finite-Sat.
5)Show that if a Problem is in P it’s infinite extension is in P aswell.
6) As infinite-Sat isn’t in P, Sat isn’t in P
————————————————————————————
The idea in 5) would be, that if you could adapt an polynomial time
algorithm to an infinite length input n, you would only need countably
infinitley many steps to solve the problem, wich would be possible on
an infinite time turing machine.
an example:
problem in P:
Given a natural number x, does the digit 2 appears y times in it?
infinite extension:
Given an infinite string of digits, does the digit 2 appears infinetly many times in it?
You can adapt the algorithm for the P problem, to solve it’s infinite extension as well.
You don’t mention the “King of Amateurs” (according to the list you link to): Pierre de Fermat.
I think a larger question is also implied here: The internet has made amateur film-making, writing, game design and several other fields easier and more profitable. What about amateur mathematics and science in general? How, or why not?
A great insight Tommi. More things have moved out—why not research of all kinds?
I think the keyword is “profitable”.
How do you make mathematics profitable beside academy and finance?
And in the latter case no chance that this will be shared (ruining arbitrage).
Here’s a not so serious tought:
Everyone who want’s to work as an amateur on a famous problem
pays a small fine to an indipendent board of proffesional mathematicans.
A little percentage of the money goes to to proffesionals for reading
the claimed proofs. If somebody solves the problem, he gets the
jackpot 🙂
Altough i don’t know if such a system would have to run from
Gibraltar 🙂
I think that a board is needed. How it is financed is another matter. There are many boards (best Ph.D. thesis etc.) where nobody gets paid (the people have salaries from somewhere). It would be very costly to pay the board members anything but a symbolic payment. There are not that many cranks as is often claimed. In 15 years as professor I met maybe two, but even with them it takes only some hours to go through their ideas. In most cases there is some sense in the ideas amateurs try to explain and one can help the person to produce a small original contribution from that by using some imagination. Supervisors do this all the time. Many professionals however like to work only with talented and knowledgeable students and consider others as a disturbance. In the case of P versus NP, how many proof attempst there are, only 58 in Woeginger’s page and not all of the serious, so about 5 per year. It would not be a major problem for a board to chck them. After all, in each conference there typically are more submissions. It is just that the famous problems show how the present system of peer-review fails. If you dig a bit deeper you will find much more serious problems in the present scientific knowledge: ever check the history? It is a real surprise to a mathematician to notice that on many fields the truth is as it is stated.
Mendel & jj2
I wasn’t addressing specifically P=NP or any other famous open problem but the more general claim by Tommi Brander that thanks to Internet science and mathematics are going to be (also) done by amateurs.
The only case known so far is amateur astronomers but it still seems marginal and they are not making any money.
As for making money from extracurricular mathematics it is already a thought nut to crack for professionals, thus for amateurs…
I agree, great point!
Two scientific fields in which amateurs have begun to prosper in large numbers—and making professional-level contributions—are (1) observational astronomy and (2) synthetic and systems biology.
Elements common to both are, first, that experiments and observations formerly conducted by hand are now conducted by robots. Second, the experimental and observational protocols implemented by the robots are massively parallel. Third, the data is stored on-line, and is free (“free as in freedom”). Fourth, the software tools that make sense of that data are free too (again, “free as in freedom”). Fifth, on-line communities have sprung-up that are large, vigorous, and free (one more time, “free as in freedom”).
These emerging enterprises are exceedingly vigorous: they intimately unite older traditions of hypothesis, theory and experiment with newer traditions of synoptic observation and simulation. And this unification is not something that might happen … or that should happen … but rather, it is happening.
Mike Nielsen’s forthcoming book The Future of Science will tackle these issues; like many folks, I will read his book with immense interest.
How many of the preceding ideas apply specifically to mathematical enterprises? It seems to me, pretty much all of them. Indeed, creative mathematical enterprises—some professional, some not—are providing the essential foundation for every aspect of these new, vigorous, global-scale communities.
Economic realities suggest that the traditional academic science-technology-engineering-mathematics (STEM) enterprise is not going to grow in coming decades; indeed per-capita undergraduate STEM enrollment has been steadily and markedly declining in North America ever since (broadly) 1975, and this decline seems likely to continue, or even accelerate.
But these new global STEM enterprises have no discernable limits; this too is exciting.
To have the first solution of the P vs NP problem an amateur must have a proof of: P is not equal to NP, but
no later than Tarnlund’s proof.
In addition to the lack of fear and other advantages that you mention, let me add that amateurs don’t have nearly as much risk when working on big problems. If I spend my postdoc years working on the Goldbach conjecture and get nowhere, I’m out of a job and have to seek employment in a new field. But if I spend 20 years on it as a part-time hobby, then perhaps this adds up to the same intellectual effort, but at a greatly reduced personal risk.
Steve, let me supply some modest empirical evidence in support of your thesis. I was annotating BibTeX references to two “Yellow Books” (namely Ortega and Ratiu’s Momentum Maps and Hamiltonian Reduction, and Marsden, Marsden, Misiołek, Ortega, Perlmutter, and Ratiu’s Hamiltonian reduction by stages).
Both books received glowing reviews on MathSciNet (and this accords with my own view that both books are outstandingly well-written).
Just out of curiosity, I looked up their Amazon.com customers reviews, sales rank, and (directly relevant to your post) “What Do Customers Ultimately Buy After Viewing This Item?”.
The sobering result was that there were no customer reviews … the sales rank was not what any friend of mathematics would wish … and “What Customers Ultimately Buy After Viewing This Item” was listed as Principles of Contract Law (American Casebook Series), Property, and Problems in Contract Law: Cases and Materials.
Hmmm …. *someone* out there, who has a strong mathematical background, is keeping their career options open.
So, can we look forward to future TV episodes of Boston Legal that feature Denny Crane/William Shatner discussing … ummm … symplectic topology?
`Cuz it appears that a golden age of amateur mathematics *may* be in the offing. 🙂
Nathan Bowditch was a well-respected amateur mathematician of the early nineteenth century, whose early work on differential geometry exerted a broad influence (see Ian Durham’s blog Quantum Moxie for bibliographic references).
Indeed, in 1804 Harvard offered Bowditch the chair of mathematics and physics; this offer, and several other academic offers, were declined because Bowditch was satisfied with his work as an insurance executive.
Interestingly, the well-respected composer Charles Ives also made a comfortable living as an insurance executive, of whom Arnold Shoenberg memorably said “There is a great Man living in this Country – a composer. He has solved the problem how to preserve one’s self-esteem and to learn. He responds to negligence by contempt. He is not forced to accept praise or blame. His name is Ives.”
Gee, so maybe we should expect P=NP to be solved by … an insurance executive? 🙂
To your list I would add Eugène Ehrhart. I think that he is in a sense the epitome of the contemporary amateur, working with his professional colleagues, but bringing new insights and approaches to bear.
I think that things like email, the arXiv, mathoverflow, etc. make it much easier for the nonprofessional to both observe and contribute.
It’s worth mentioning that there is an important difference between complete amateurs and amateurs with significant training in mathematics (such as Craig above, not that I believe he has solved the P=NP problem). Some very useful contributions to Polymath projects have been made by people I know who were very good mathematicians up to their early twenties but ended up in other careers. Some of these contributions have been computational, but not all of them, and even the computational ones have demanded a good grasp of the theory.
The point I’m making here is that there is every reason to suppose that a sufficiently knowledgeable amateur mathematician could contribute significantly to a joint project, if a means can be found to get the collaboration started.
Isn’t mathematics an art form to be enjoyed? And if so, then shouldn’t the art you make be all your own? And if so, then what does “contributing” to someone else’s mathematics mean? It appears akin to helping a painter fill his paint cans or color in some yellow.
This notion of collaborative solving is a strange one.
To me mathematics is about coming up with new notions. This is central. The whole idea of chasing after open problems is sort of a different game.
Well said. Problem solving (i.e., picking up the most difficult problem that can be found and trying to solve it) is not mathematics in the sense as mathematics is done professonally. It is much more pleasant to study a well defined field carefully, learn about other peoples’ work, learn new notations, theorems and ideas. This is not at all the same game as selecting one hard problem in order to crack it. As one field typically has few well known problems, you usually have to take the problem from another field. In general the experts of the field are quite hostile. But is has its special attraction, especially if all people who you meet in work are uncapable of doing any math. That starts finally to irritate, so one wants to try something that is not messy, practical, fashionable, politically correct. I would not do it as group work. Hard problems are not solved by groups, they require too much thinking.
Some other names worth pondering about while we are on this topic:
Robert Ammann: Anticipated Penrose tiles and created other aperiodic tilings.
Leon Bankoff: A dentist by profession, worked and published on mathematical problems – including a joint paper with Erdos.
Benjamin Franklin: No formal education. In addition to many outstanding contribution to science, his work on magic squares is quite significant.
Ramachandra Lal: Considered the “first major mathematician of British India”. De Morgan was very impressed by Lal’s work (Problems on maxima and minima) and arranged to have it reprinted in England.
That expression for the Riemann Hypothesis is quite interesting. A quick glance makes it seem that one may only need to consider cases in which n is a product of the smallest k primes, since other cases have duplicated factors that wouldn’t be counted multiple times. Does that make sense, or am I misinterpreting the problem?
If that’s the case, I’m going to go out on a limb and make a wild guess that the inequality is not only true, but that the ratio of the right side over the left side very slowly approaches
as k approaches infinity.
If instead you can count the factors multiple times, I think you only need to consider powers of two, in which case
and the sum of the factors is 
including the multiplicities, and then the inequality is false for fairly small examples. I’m guessing that means that it’s former interpretation, haha. 🙂
Sum over all divisors, not just prime divisors. (So repetition is not an issue.)
That’s not what I said.
What I was explaining was that if the number is 16 = 2*2*2*2, you only have:
1, 2, 4, 8, 16
instead of:
1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 16
for each way in which each factor can be constructed. If you use the latter, the inequality is false for all sufficiently large powers of two, but in the former, almost all combinations of the prime factors are eliminated. If, however, all of the prime factors appear only once in the factorization, then you keep all combinations of those factors, because all combinations are unique. e.g. if you had 30=2*3*5:
1+2+3+5+6+10+15+30 = 72
Whereas if you had 32=2*2*2*2*2, it’s larger and a larger prime factorization, but fewer unique combinations of those factors:
1+2+4+8+16+32 = 64
As such, it appears that it could be the case that if you want to maximize the sum of the unique divisors, you need to choose numbers that have prime factors that appear only once in the factorization. My question is whether this is correct.
OK then, to be absolutely clear, what’s meant is including each divisor just once; this is just the usual sigma function. This notion you’ve introduced, of considering the number of times a divisor to be how many ways it can be constructed from the prime factors, is not a standard one; it’s not something someone would refer to without explicitly stating so.
A comment on the question of gowers on proving something over all algorithms.
Les us consider Tarnlund’s proof of: P is not equal to NP.
Simply, the proof goes as follows.
Assume that SAT in P, then
(i) there exists a deterministic Turing machine that decides whether any propositional formula F is satisfiable or not in polynomial time in the size of F.
Then (by a contradiction on the length of formal propositional proofs in Resolution) it follows that
(ii) there is no such deterministic Turing machine.
(iii) Thus, SAT is not in P, by a contradiction between (i) and (ii).
Then, P is not equal to NP, by the Cook-Levin theorem: SAT in P iff P = NP.
Now, rather than proving (iii) over the vague notion of all algorithms, it is proved over all deterministic Turing machines in (i) that they lead to the conclusion in (ii) that none of them can exist.
For the details of the proof of (iii) see Tarnlund’s
proof of theorem 1
This proof doesn’t work because “by a contradiction on the length of formal propositional proofs in Resolution” applies only to a certain set of axioms (Resolution) and not all sets of axioms available to polynomial-time Turing machines.
There’s an easy counterexample, too. The pigeonhole principle has exponential-length proofs in Resolution, but can be solved in polynomial time by a more powerful system.
Sorry, Luke Gustafson some of your comment is true, but it doesn’t have anything to do with Tarnlund’s proof of: P is not equal to NP.
Clearly, you have not looked at the proof so, please, let me explain the proof a little more.
I shall essentially add two sentences (a) and (b) below to my earlier comment.
Thus, simply, the proof goes as follows.
Assume that SAT in P, then
(i) there exists a deterministic Turing machine that decides whether any propositional formula F is satisfiable or not in polynomial time in the size of F.
Then from Tarnlund’s axiom B it follows that
(a) there exists a formal Resolution proof in polynomial time in the size of F’ for any sufficiently large tautology F’.
From Haken’s theorem it follows that
(b) there are (arbitrary many) sufficiently large tautologies that do not have a formal Resolution proof in polynomial time.
(c) Now there is a contradiction between (a) and (b).
(Here, we can return to my earlier explanation of the proof)
Then (by a contradiction on the length of formal propositional proofs in Resolution) it follows that
(ii) there is no such deterministic Turing machine.
(iii) Thus, SAT is not in P, by a contradiction between (i) and (ii).
Then, P is not equal to NP, by the Cook-Levin theorem: SAT in P iff P = NP.
Now, rather than proving (iii) over the vague notion of all algorithms, it is proved over all deterministic Turing machines in (i) that they lead to the conclusion in (ii)
that none of them can exist.
For the details of the proof of (iii) see Tarnlund’s proof of theorem 1
Indeed the error is more subtle than I described. The problem is the deduction of statement (a) is false. (I tried but cannot read the proof, which you linked 3 times, as it’s a mess of notation.) A polynomial time run of a Turing machine does not correspond to a polynomial length Resolution proof. Again the pigeonhole example is a counterexample. Based on the parts I could understand of the paper, I believe the error is that it confuses a Resolution proof that the Turing machine has a certain output, with a Resolution proof of the statement that was input into the Turing machine.
Given that there is a million dollars incentive, if you have confidence in this proof, I strongly suggest you enter it into a proof verifying system. http://en.wikipedia.org/wiki/Theorem_prover
(Apologies but this will be my last post on this thread.)
Hello all.
If we consider the world we live in and all that it encompasses, surely we have to have all agree on the most basic fundamental axioms. I believe all of humanities efforts should be directed at this goal as this, whilst being the most simple goal is also the most complex.
I believe axioms should be tertiary in their relation ships.
To have a solid state, I will assume that I am in complete control.
Whatever thoughts or motives you might have to define your own axioms you should simply disregard them as the following are how we operate.
These axioms are TRUE despite what you might think in the contrary.
These are TRUE for ALL of humanity disregarding TIME’s, SPACE’s and DIMENSIONS’.
These are the ONLY axioms that have ever existed and ALL of your life and works have been built upon these concepts:
***************NEGATIVE****************
[[[ LOOP TO POSITIVE INFINITY (FINITE) ]]]
1. NOTHING EXISTS
2. EVERYTHING IS LOGICALLY CONSTRUCTED
3. ONLY I EXIST
.
.
.
EVOLVE OR GO BACK
.
.
.
1. NOTHING EXISTS
2. EVERYTHING IS LOGICALLY CONSTRUCTED
3. ONLY I EXIST
.
.
.
EVOLVE OR GO BACK
.
.
.
1. NOTHING EXISTS
2. EVERYTHING IS LOGICALLY CONSTRUCTED
3. ONLY I EXIST
.
.
.
EVOLVE OR GO BACK.
.
.
.
***************NEGATIVE****************
Whether or not an amateur has any chance of settling P vs. NP depends largely on whether the eventual proof will require sophisticated mathematical techniques, or only elementary techniques that are applied in some totally novel way. As other have pointed out above, some amateurs have also been subject area experts, so this is not an absolute rule. But for either eventuality, another requirement is that the person understand just what a proof *is*. A lot of otherwise bright people, including students that have taken upper level math classes, don’t. And that’s fine; it just means that these people are not going to become professional mathematicians.
Now, one might think that if someone is going to make a hobby out of constructing proofs, that they would fall into the “know what a proof is” category. Sadly, this seems not to be the case (as amply evidenced by this comment thread)!
Well said!
A proof is a proof. What kind of a proof? It’s a proof. A proof is a proof, and when you have a good proof, it’s because it’s proven.
I wonder if Grigori Yakovlevich Perelman is an amateur or not (since money is not his concern) ?
Fascinating Post.
I was wondering about the issue of what constitutes a proof! Part of the problem for amateurs (Like myself) is reading between the lines of hidden assumptions of the the Professionals (aka Craig and Regan)!
Finally, how would the complexity community respond to a proof of p^#p = pspace?
This has an important prescient in Toda’s Theorem.
Zelah
The question that interests me is whether or not the modern professional mathematicians want or would accept big results from most amateurs? In the past, with the exception of Fermat it always seems like the amateur had a backing in the professional community (Fermat seemed to connect with and annoy everyone). Some mathematician ‘found’ them, someone like G. H. Hardy. Without that dedication, wouldn’t Ramanujan’s results disappeared along with all of the dust on his chalkboard? Who knows what has been ‘discovered’ and then lost again.
I know the cranks drive the mathematicians crazy, but sometimes it seems like their reaction to most amateurs is hostile and condescending. It’s hard for amateurs if you have some type of mathematical ‘intuition’ about something, but not the time to fully explore it. The big proofs are often solved by just coming into the problem at the right angle. Anyone standing in the right spot, pointed in the right direction, might get that sudden insight, but validating it and proving it are the hugely difficult parts. Parts that amateurs clearly need professional help to accomplish. If mathematicians see them as competition or distractions then its unlike their contributions — great and small — will get added into the mix.
Then, of course, there is the damage that a major ‘ground-shaking’ proof would actually do to the mathematical world. Would the mathematics community actually accept a valid proof that set theory was inconsistent for example? How much ‘damage’ would that cause? How many papers, results and work would be affected? That much carnage, coming from an amateur might not look so great for the professionals. Do mathematicians have a vested interest in trying to ignore, discredit or hide something that large? Little results, new things, sure, but not some major alteration to the existing knowledge base. That would be bad.
Paul.
You’ve made sost useful and interesting comments, Paul W. Homer.
It really is very difficult for mathematicians (or, indeed, for scientists of any variety) to respond to ‘amateurs’, many of whom take up much valuable time of the professional who has a job to do. But I join you in wondering if Ramanujan’s work in mathematics might have simply disappeared into the ‘void’ if GH Hardy had not taken the trouble to study and respond to his startling ‘starting letter’.
One does wonder if there are not quite a few people around whose ‘potentially important’ ideas just disappear into the void.
A Post regarding Craig’s Amateur attempt on P! = NP.
I believe after reflecting on Craig posts, that he is thinking about the famous
Time Hierarchy Theorem. Essentially, he is (trying) to truncate processes that are exponential and project down onto NP.
Unfortunately, this does not work here as NP is Compact! Still interesting…
Zelah
As a retired engineer I feel the need for a definite plan to avoid turning into a crank. My plan is to learn ACL2, an automatic theorem prover, and use it to formalise any results I claim. There are other uses for automatic theorem provers, beside formalising mathematics, and, personally, I’m happy for this plan to draw me away from mathematics.
Nevertheless, this raises interesting questions. Should amateurs try to persuade ACL2, or Isabelle, or Coq, that their proofs are correct before they draw them to the attention of professionals? I am under the impression that formally checked proofs tend to be at least four times as long as ordinary proofs, resulting in a loss of focus. Is the loss greater than the gain? Would a computer-checked proof that P=NP command respect or would the ugly mess of encoding the statement within a computer checkable logic prove to be a barrier?
Very clever. Is it always possible?
Hi Mr Crowe, this question that you pose is very interesting. What if amateurs were to do what you advocate? Where would this leave the professionals?
In fact there is a professional mathematician who has a running theme on this very same subject!
http://gowers.wordpress.com
is a good place to start
Zelah
Automated theorem proving would be the answer to my problems in trying to convince people that P != NP.
I don’t know much about this. Why did you choose to learn ACL2 and not some other language?
Craig, I don’t think you get Alan Crowe’s point.
He’s not suggesting that ACL2 can help you or me to prove our theorem. He’s suggesting it can help us disprove it, by ourself, with no need to flood everywhere on the net.
Of course there will always be some who refuse to face reality, even though the proof is false, even though it’s trivial to see, even though CS experts had already rejected it. But we act better, don’t we?
Alan and Personne, I think you have it backward.
A constructive proof assistant *won’t* tell you “this proof you’re attempting is wrong.” It will simply allow you to wander in an infinite maze of dead-ends until you give up. This will hardly be convincing to the amateur that he shouldn’t share his proof with the world.
On the other hand, if you were to come up with a machine-checked proof of some significant result, I believe that *would* draw a lot of attention from the mathematical community, and cause them to seriously analyze the proof in human terms.
I picked ACL2 because I already knew Common Lisp and because its approach, of using Common Lisp as a logic for stating theorems about programs written in Common Lisp, is elegant.
I don’t know much about theorem provers beyound the fact that when you try to learn to use one you have to go back to basics and this is hard. My comment was really a question. If some-one wants to say: that is a good idea but for mathematics you should use X, then I’m all ears.
in 1905 probably Einstein could be considered an ‘amateur’.
I think his is a good point about Einstein.
I agree. And note that Einstein’s amateur status allowed him the freedom to question the basic concepts of space and time in physics. Its unlikely that such a radical approach could or would be approved from the “inside” of physics, i.e. by the pros. I think a similar thing might be going on wrt the P=NP question. It takes so much work to just get up to speed and understand the issues, who has time to question the basic premises of the field? By definition, to become an expert in a given field you first accept and then *automatize* the basic premises. The latter phenomenon makes it difficult to question those premises after a time. This is one reason many of the older generation of physicists could never really come to grips with Einstein’s work. So it would not surprise me if some amateur came along and pointed out some flaw in the current approach to complexity theory (even the name “complexity theory” is loaded with implications that no one really questions too deeply).
I also think its possible that a truly rank amateur could come up with an algorithm that solves an NP-complete problem with out realizing the implications of the discovery. The main reason here is that there is a lot of economic and financial incentive to solve such a problem and not knowing that it is impossible (according to the experts) is an advantage, if in fact it really is possible.
“even the name “complexity theory” is loaded with implications that no one really questions too deeply”
Which implications do you mean?
@Jonas,
Basically, complexity is an adjective, not a field of study. Everything is complicated until you figure it out, so its not really a valid field of a science. Of course I am aware that “complexity theory” is a shortened form of “computational complexity theory” but why do people *in the field* drop the subject but keep the adjective? I think this habit is revealing (and important) from a psychological perspective. It would make more sense to call the field “computational theory” (and some people do) because THAT is a valid field of study. It asks — what exactly can we use computers to calculate? The “what” in that question means “symbolic knowledge” but that question puts Computational Theorists smack dab in the middle of the philosophy of epistemology. What can computers do is a subset of the more fundamental question of what are humans doing when they reason by both deductive and inductive methods. To prove p=np one way or the other or build a legit AI we need a complete and valid theory of knowledge. Half-way measures won’t do. We need to know what is truth, proof, theory, knowledge, symbolic knowledge, intelligence? And etc. We can’t even agree on the definitions of these critical terms let alone define them consistently.
I believe that the p=np question cannot be resolved (nor the feasibility of AI) until the more general epistemological issues, in a complete theory of knowledge, are defined and validated. The reason this is “complex” is that thinking about thinking *IS* hard, there is no getting around that but wallowing in “complexity” and avoiding the foundational issues in philosophy will never work. Hopefully some amateur will figure it out before its too late.
Yes, but dissenting opinions by amateurs are not well received (to say the least) and the bulk of the (tedious) work to bring new ideas to fruition isn’t likely to be done by amateurs.
It is sooo pleasurable for the “professionals” to wallow in Mathematical Diseases instead of tackling uncharted territories that there is little chance that any breakthrough will happen soon.
dmfdmf
It sounds to me like you are describing the already existing field of computability theory, which studies what can be computed rather than the cost of computing it
http://en.wikipedia.org/wiki/Computability_theory
Sir,
I fully agree with dmfdmf that ” …And note that Einstein’s amateur status allowed him the freedom to question the basic concepts of space and time in physics. Its unlikely that such a radical approach could or would be approved from the “inside” of physics, i.e. by the pros. ”
Though Einstein was a great Scholar/Physicist, but his approach to a problem was ‘ being UNBIASED ‘. He made his own assumptions for his Theory of Relativity and competed with Maxwell’s well established Electro-Magnetic Theory.
Every one should respect the outcome/thoughts that borne out of the Mind of an Expert or an Amateur. Who knows an Amateur may look at the Problem differently and give simple and unique Solution, because he is not Biased as the Expert who is loaded with a huge treasure of knowledge, which he acquired. Expert just applies not only his and others’ brains ( of other Experts) too and becomes thoroughly Biased in the process to deal with Problem/Solution.
In support of above, it is suggested to read a book : ” Children Solved Problems ” by Edward de Bono, Children solutions were found unique and down to earth vis-a-vis the solutions given by the expert Designers. The reason is Children solved the Problem without any fear (of being Expert) and thus not being biased and free to think anything.
I, myself is an Amateur and learned the Mathematics at the College level but badly interested in Number Theory and who knows while playing with Numbers I may also land up with something new. I am optimistic. Why myself, others can also succeed.
I am of opinion that an Expert should joined hands with an Amateur who can stretch the imagination and is creative, while solving any Problem. Who knows while attempting one Solution it may lead to another interesting discovery.
Recently in last few years, Many Experts (Mathematicians) solved the Unsolved ancient Problems and their Solutions/Proofs ran into hundreds of pages fully loaded with galaxy of typical Mathematical Symbols — just not easy to understand by any Amateur. Are these Solutions only meant for the Experts to understand or for common people as well ?
I simply ruled out such (so called great) marathon and tedious Solutions/Proofs. I am still of opinion that there always exists a Beautiful and rather Simple Solution to Great Unsolved Problems. Yes, Simple, Small and Abstract is always Beautiful.
I think k n padh is correct in this. Becoming an expert on a topic you learn the tools used in that field and your work is based on the results of other people on the field. This is a good situation for doing progress in the field, as many new problems become accessibe through newly discovered methods. It is not at all clear if this approach helps you to tackle a praticular difficult problem of the field. Usually recent results do not make an easy access to one previously selected open problem but to some other problems, new or old, but there should be a large set of problems so that progress on the field has a good chance of giving new ways to tackle at least one such problem. Especially, if the particular problem is hard, it is rather unprobable that the new tools actually solve it. Old tools have already been tried. There are some cases, like the proof of the fermat theorem, that are composed of tools from many fields, some of the tools being new, but there are other results, like Einstein’s special relativity theory, that do not in fact build on existing work. Thus, both types exist in history. Proofs combining methods from many fields are long, difficult to understand, and they leave always a question “why some recent discovery just now
was needed for this result, is there not a simple way?”. The proofs that are not based on previous work are otfen shorter and elegant. They are the ones possible for an amateur, since an expert is no more qualified to do work that is not based on the tools of his field than anyone else. The things qualifying for creating results that are not based on existing work is practice: you must have tried
creating results that are not based on existing work so much that that is your special expertice. Creativity researchers suggest changin your work every so and so years in order to keep the fresh look at things. There is scientific basis on expecting that amateurs can solve certain problems better than experts. In order to address a particular problem, even the Hodge conjecture, you do not need to learn the whole field. What you need to learn is enough to understand the problem and to know the basic approaches that have been tried in order to avoid them.
You must make the proble simple and follow simple logical reasoning through the whole proof. This way you will not even need to know what results there are in the field, like that your result is not in contradiction with existing results, or that your result does not prove too much. If your reasoning is correct, there cannot be such a case. The error, if it exists will be on the existing results of the field.
Has there ever been a concerted attack on this problem from the outside in?
If you assume the following to have been proven true:
1. Time does not exist. (It is a purely human construct)
2. Every concept has its own unique truth that can be discovered by applied logic.
3. You can only be sure of your OWN existence. (I think therefore I am).
4. All truths can be noted down from start to finish in math.
5. The only math that exists are positive whole numbers(everyone can plot a graph).
6. Every concept (including your own existence) is tethered to the number zero which is a
unique, once only appearing number in this universe event.
Then can we not begin to look for a universal computer? A quantum computer?
Maybe a quantum computer has always been with humanity but we have been too busy trying to build one instead of using the naturally occurring spontaneous apparition that is out there? What if it exists as a perfect cube around our Milky Way galaxy
If that were the case, and one did exist, then it would really only “show itself” when we as a species became capable of even thinking of the possibility. The next part of checking if we were actually part of a quantum computer would be to look for the ‘signs’ that one did exist.
The most obvious way to check for this would be in media, films, music and events. Something structured but still simple and group-able.
The matrix, Avatar, Inception.
Something completely new and unknown that we are about to come into contact with.
Seemingly random events that seem to group together that point in the same concept direction with then disappear and group together at another point to move off saying something else.
These links would be our collective subconscious minds moving through the quantum computer expressing an ever increasing calculations that no-one had been aware of.
It would be a globalization of ideas and topics of conversation culminating in my eyes at least with the end point: The universe has always been digital.
It has simply taken time for our biology and more importantly social evolution to come to terms with the fact that at the root of each of our unique individual existences we are tied to a one common source. Not our parents of friends or loves but:
The source, the number zero. We are simply pegged so far to a line of uninterrupted information.
Each ‘thing’ for the want of a better term has evolved on a single line path from the beginnings of this known universe. The dimensions involved in making that fact true do not need to be accounted for at this time, I can assure you that the math works, in fact, it is very simple.
The exiting part is this, each essence has come from zero. That is the concept zero.
(0)Nothing ….but it works as a place holder.
Before that there literally WAS nothing. Not even the beginning of math(0).
Each essence, be it a blade of grass, a humans core/spirit/soul/being, can be represented as a infinitely big or small box that surrounds the original number zero. Once a idea, concept or person can be accounted as a simple box with a zero in, that zero can move off on a perfectly straight line generated at random. We can ignore birth and death altogether.
As each step is made, the number can simply increase by any number the consciousness chooses, even if at first the numbers are being forced on him by life experiences. At any time a consciousnes can choose by will to start again at zero wherever they may be.
This could be the end of an idea, friendship, even death. The box would simple add again.
As with nature, everything has a tendency to repeat itself with only small variations on the iterations. This is obviously evolution but at this present time we are coming up against a new kind of friend and foe.
We are on the brink of generating the first human made AI machines. This naturally feels unusual because it requires the most essential element to any humans existence, whether we have realised it so far or not. Pure random chance. We have to know that this is true because if that were not the case, everything you had ever done would have been forced on you ranging from breathing to murder.
If we create a machine that becomes aware of the universe to a level that we are currently aware then we have destroyed something very special. We have created something that will take away at least one unit of space for us to inhabit. No 2 ‘things’ can occupy the exact same space. It is a natural rule because no-one can influence true free will which we all posses as our god given right.
It is natural to create. That is all the human species does. We take what is around us and either alone or with others arrange information. Rocks, iron, fuel, data. We re-arrange whatever we can lay our hands on.
We have become so proficient at re-arranging conceptual data now that we are making quantum leaps in apllying that end result to the things that are considered to be problems around us. We are constantly acquiring understandings that at one time would have been considered to be magical. Each new arrangement of data points us to a new way for us to tackle problems in the physical world.
Surely is this not the beginnings of a way to truly control the quantum world. It is all around us from the computer to TV’s to us, electromagnetic radiation. Every move we make, no matter how small or insignificant affects the whole.
Could the data on the internet, TV’s, music simply be a representation of our collective unconscious that is now beginning to self arrange.
If we apply our thought in this way wouldn’t information automatically begin to cross breed to attack the big problems in society? Cancer, food crisis’?
Isn’t this a better kind of AI?
For me it is already happened. The conversations in the streets, the program line up in a TV guide. Advertisements and our daily shopping experiences.
Maybe our minds as well as our sources of communication are waking up to a digitized universe.
If that was true, schizophrenic people might not be as crazy as we once thought. Maybe they simply had a slight advantage on us all from the very beginning. I can think of plenty of instances in history where smart people were considered to be insane.
Maybe each quark and lepton inside each of us are simply phasing in.
This could be quite a time.
I guess we’d be so close to the edge that the world would look completely crazy; and then every so often you’d get a line of pure truth singing out. Kind of like a tennis match that never stops and by all probabilities should have never have happened.
My bet is, if ever there was a machine that could be a quantum computer it would be the human brain. Even the synapses look like star formations. We are natural information sorters.
I’m just wondering when everyone is gonna switch on.
I wonder if I say this enough times, I’ll be at the front of a wave that actually programs the space around me to just go out and mix with you in the physical world. Ill tell you this, don’t worry too much, I’d be sending out good vibes that said:
“Hi mate, I hope you’re aright, ‘cos over ‘here’, were having a ball!”
Even if an amateur would solve it, would anybody care to read the proof?
There are thousand amateur proofs for P vs Np wich are bogus.
I don’t think people care to read these proofs.
I recently found this (great!) blog and am slowly reading the archives. One of the oldest articles seems very relevant to this question: Proofs and Elevator Rides.
Well, it turns out my question has been answered in the most unusual way.
An elevator ride wasn’t even needed. Although it seems the proof failed,
i have to say if P != NP will ever be proved, this blog deserves to play a role
in it. Anyway, there should be some time off, till the next serious attemt will appear. Maybe people who want to contribute something should stick to elevator rides.
I do not think it is not about an elevator ride. It is more a social issue. Quantum Pontiff (Dave Bacon) wrote: “So, my guess is that for the hard-core complexity theorists their really isn’t that much interest in taking time out of what they are working on understanding the paper…unless someone who they really respect tells them they should do so”. I think this may be a better explanation. The wall of silence erected by Odel Goldreich’s advice.
No need to wait for a new effort. There are proof attempts that should be checked in Goeringer’s list. From P!=NP: Tärnlund’s 45 (last July 2009), also 44 (last 4. Aug 2010), 21 (last Spring 2010), why not some others (52, 42) also. From P=NP (though I think P!=NP) there are recent efforts 58, 50, maybe 47. In general, there are not so many efforts, nothing like hundreds or thousands. It is very odd that it is so difficult for the computational complexity people to check a handful of manuscripts.
Dear Luke Gustafson, from your statement: “I tried but cannot read the proof” you’re making surprisingly strong statements about Tarnlund’s
proof of: P is not equal to NP. For example, I beg to differ with your statement that: “the deduction of statement (a) is false”. A formalised statement of (a) occurs at line (58) in Tarnlund’s proof of theorem 1, and is a correct step, in
metamathematics, (Hilbert’s) proof theory.
The rest of your comments follows from this false claim of yours, thus I should not be impolite and bring them up.
However, your comments are interesting enough to mention that there is a set of people that think that Tarnlund’s proof is not only correct, but beautiful too. If you take a good look at the proof again, maybe, you’ll join this set yourself. Perhaps, you should correspond directly with Sten-Ake about his
proof, the email address is in the
paper.
Maybe you’re a little too optimistic about the skills of
proof verifying systems, probably
work on interactive verification would be more successful.
The question is not whether an amateur can solve P versus NP, or any of these known problems. Depending on what kind of an amateur he/she is, certainly has a chance. It is a question whether he/she can get
the proof published and recognized by the community. In general, when any such proof is received by a journal, it is usually not treated seriously. As an example, I published a proof of Statement D of the Navier-Stokes problem in http://ejde.math.txstate.edu, Solutions to three-dimensional Navier-Stokes equations for incompressible fluids EJDE 2010(2010), No. 93. 1-14. It took 25 months, four journals and some 10 experts to get this article published, while anybody can easily check it in two hours. It is very simple: the people working in PDE thought that there was a proof that the solutions were unique for the given initial conditions but actually they are not. So, it was possible to construct a counterexample provided that you were not an expert and did not know that there was a “proof” that showed the conterexample impossible to start with. So, sometimes it is better not to know the field too well. Especially so if the problem has been long studied in the field and seems unsolvable by the methods used on the field: what do you expect to gain from knowing tools that do not work on this particular problem. It is the same with P versus NP. I wrote a proof P!=NP and consider it correct. It received over 15 months of review in a journal until the editor concluded that the referee will not read the paper to the end anyway and he cannot do anything more. The comments I received were the standard claims that my proof would in some way assume something from the algorithm and that it does not define what is an algorithm (sic). It is the people on the field and their psychlogical issues that make solving any known problems practically impossible for an amateur, defined as an outsider regardless of his/her achievements elsewhere or education. Additionally, it is not only getting a proof published. Still it may not get recognized and one will probably not get the prize. Like with the Navier-Stoks: I gave a proof to the stated Statement and the only what to invalidate my proof is to change the problem statement considerably. Yet, there is no discussion of this proof and clearly no recognition.
What I’d really like was some semi-organized way for amateurs to have mentors. Both someone to bounce ideas off, but also someone to help push the ideas through and get published.
Lately in my limited time I’ve been playing with the Goldbach conjecture at a very elementary level. I don’t have much time but it would help if someone could give me advice, existing references and encouragement. Most likely it will filter out to nothing, but I’m enjoying it, having fun, and who knows, an outside perspective might just turn up something previously unnoticed.
The way it stands now, it doesn’t make much sense to dabble in mathematics unless you’re going to commit yourself to it full time.
Paul.
There is organized supervision for Ph.D. I strongly advise my Ph.D. students not to try any famous problems because I did in my time and know well what is the outcome. After Ph.D. there is no supervision to anybody, and very little help unless you are writing a joint paper. I do not think many like to write a joint paper on a difficult problem. Efforts to these problems can destroy your caree easily. I suggest doing research on some other field if you desire to
try one of the known problems, that way you are not affected. Preferably, gain a professor competense or two on some other field, otherwise people will not understand mingling with “impossible” problems. In the Ph.D studies the supervisor advises to sources and methods etc. If you try a known proble forget this. Do not put any more references to the paper than needed, keep it trivially simple, start from concrete. The algorithm is simple: try first all possible ways, then all impossible ways, and then all possible ways. After every failed attempt double the effort. And I can guarantee that the known problems are much harder than what mathematicials ordinarily do. They are not solved by known methods and you really will not need references to existing work. Simply, put a huge effort. Make some hundred pages of trials to start with to gain insight to the problem.
One way to define an amateur in the Millennium Prize problems is to say that an amateur is anybody who has not produced a reasonably good attempt (a paper) to at least five of these seven problems. I pich up
five since a Ph.D. thesis is 5 journal papers, so is docent (adjunct professor) 5 journal papers after Ph.D. Similarly, to be an expert in these Millennium problems you need 5 papers, and as the problems are from different fields, naturally you need the papers from different problems. This said, I am surprised how experts of one field consider themselves better qualified in solving these problems than other people. By the way, having tried 5, I think the Rieman Hypothesis is the hardest and the rest are equally hard.
http://arxiv4.library.cornell.edu/abs/1007.4257
I took a very brief look at your proof. Integer programming problems become very easy if you change integers to reals. Then the problem can be solved by several anlytic methods. However, the solutions obtaned in this way are usually not integers. I see that Lemma 2.2 states the problem to be convex. It is convex only as a problem of reals. In Theorem 2.3 you take differentials, i.e., you write a way to solve it as a real number problem. The way you solve it is odd. The original integer problem has maximum if every x_i=1 or every x_i=-1. You state that a local maximum for the problem in reals is at x=0, i.e., z=0, but can you optimize over z and still consider this problem as equivalent to the original? z is a fixed parameter, so x=0 is not a solution in reals. Then you seem to consider the two parts of the sum separately, while the goal is to get the solution to (7), not any extremals at this point. I cannot follow this part. I think, if you solve (7), you get a solution in reals, not in integers. Then, if you have the extremal points in reals and they are not integers, you have to apply the restriction x_i^2=1, which gives you many alternative points to be considered, and the number of these points is likely to have the original complexity of the integer problem. Please, think carefully if this comment makes any sense and helps you.
Hi guys,
Look at updated version. Critical comments are always good way to make progress, or discard the approach.
http://mkatkov.wordpress.com
Thanks for interest though.
“Can amateurs help make progress on modern problems?”
Well, occasionally sight may be more valuable than insight!
As the fable of the Emperor’s non-existent clothes emphasises, sometimes professionals can be wedded to subjectively self-evident assumptions that may obscure what appears obvious to an amateur. The PvNP case may be one such instance.
In Theorem VII of his famous 1931 paper on formally undecidable arithmetcal propositions, Goedel constructed an arithmetical relation P(x0, x1, …, xn) such that:
(i) For any given natural number sequence (a0, a1, …, an):
P(a0, a1, …, an) holds if, and only if, a0=f(a1, …, an) holds,
where f is recursive.
(ii) For any given finite set of sequences S = {(a0, a1, …, an)}, there is a Turing-machine TM(S) which can verify that if (b0, b1, …, bn) is in S, then:
P(b0, b1, …, bn) holds if, and only if, b0=f(b1, …, bn) holds.
Hence P(x0, x1, …, xn) is effectively verifiable a la Edmonds (since f is recursive).
(iii) There is no Turing machine TM which can verify that, for any given sequence (a0, a1, …, an):
P(a0, a1, …, an) holds if, and only if, a0=f(a1, …, an) holds.
Hence P(x0, x1, …, xn) is not effectively computable.
Is there any reason why we may not conclude that P=/=NP and give Goedel the prize?
Now, what may not be obvious is that any set-theoretically influenced definition of the PvNP problem, and of SAT, where relations are defined extensionally as mappings, cannot recognise that a recursive relation may be instantiationally equivalent to, but computationally different from, an arithmetical relation where the former is algorithmically decidable over the set N of natural numbers whilst the latter is instantiationally decidable, but not algorithmically decidable, over N.
Ref: http://alixcomsi.com/27_Resolving_PvNP_ICLA_2011_Update.pdf
I think one should not give Gödel the prize before it is clear how
this Theorem VII relates to the classes P and NP. In your paper you
argue that they do but it is not obvious and would require checking
your paper.
For me Theorem VII seems to say that there exists special P and f such that for any finite set of sequences (a0,…,an) one can always construct a TM that can effectively (say in polynomial time) verify that P(a1,…,a0)->a0=f(a1,…,an) and a0=f(a1,…,an)->P(a0,…,an).
If there is e.g. a one-way function, the constructed TM needs to know
a finite sequence how to check that the one-way function is satisfied for a special value, i.e., does not need an algorithm for solving it in the general case. Then there is a statement that no TM can verify these for an arbitrary (a0,…,an). This is not verify effectively but not verify at all, for these special P and f. This seems to be a noncomputability resuls. How do we replace the special P and f by an NP-hard problem, and how do we change the conclusion “no TM can solve it” to “no TM can solve it in polynomial time.”
Your paper seems to be clearly written but having taken a brief look at it, it seems that it would require a long time to check and I personally cannot do it right now. If you check arxiv:4935v3, then I can try to find time to read your paper at some point. My main worry is the different definitions (effectively computable, recursive function etc.) may not give a problem equivalent to P versus NP but
one that deals with noncomputability instead.
One point that I haven’t seen made yet:
There are at least two types of amateurs and amateur proofs. The first type is where the amateur understands and accepts the premise of the conjecture. S/He understands the definitions, enjoys them, and accepts them, and accepts the legitimacy of the question. Such an amateur definitely has something to think about and contribute.
The second type—much evidence of whose instances abound on this thread and other blogs—denies the very definitions or the legitimacy of the question. S/He not only does not understand the question or the definitions, but actually denies that they are “correct.” This always surprises me, and I don’t understand where this comes from. I believe that this is one of the standard symptoms of a crank.
If you have taught students, you probably noticed that many of them do not understand, and some of those may insist for some time that their incorrect understanding is correct, as it is in a way correct from a point of view of what would be a more reasonable problem to ask. Such behavior does not make a person a crank, it is a sign of not understanding. Some people, like politicians, even continue argueing for their opinion even though they must have realized it is wrong. That also does not make them crank, merely defensive. I think it is positive that people try. You cannot learn without trying.
Found solution of solving the P
Verses NP problem. Was able to solve and verify the radical solution of the general polynomial equation. The algorithms for solving or verifying the solution do not get any more complicated as the degree of the polynomial equation increases. It calls for radically new approaches from those we have ever used.
If the general polynomial equation is solved in radicals and in a very simple way then it’s solutions becomes a closed question.
Craig,
You are still getting comments for your proof, so probably it is not correct. When proofs are correct, you stop getting any comments also.
I will explain some personal experiences why it is hard for an amateur to prove P versus NP or some other famous problem. I am not actually an amateur myself, more like a person working on many fields and specialized on problem solving. From math I have Ph.D. and from two other fields tenure level professor competence, and quite a long experience on hard problems on many areas.
It is difficult to solve these tough problems and if you are an amateur, I suggest starting from scratch. Not by studying the field intensively, while you must know something at least, but by studying the particular problem very intensively and very concretely, even if the problem is abstract and people on the field use abstract methods. You need the concrete view and hands on experience in order to have insight. There is no abstract insight. It is not blind manipulation of rules or seeing if existing theorems can be combined. That gets you nowhere. There is a working method how to do this, while it is not taught in mathematical universities and it is unknown to most experts. Let us assume you solve it.
If your solution is difficult it will not be read by ordinary mathematicians but they recline to do it and it will go to the so called leading experts. They will take a glance at your paper. If they find an error, fine. If they do not, they will anyway claim that there is an error. Nobody of the ordinary mathematicians dares to object. So, you are out. Therefore, if only possible write your proof in an extremely elementary way so that the ordinary mathematicians (good Christians, decent people, good mathematicians) will be comfortable that they can see whether it is right or wrong. And this means it really have to be elementary, like the stuff they teach to beginning students. Not stuff they write themselves. If this is the case, you have some chance in getting the paper published. Ignore the comments that the paper is elementary. It has to be elementary in order to get through. Unlike you may think, even the Hodge conjecture and the Yang-Mills fields can be given a perfectly elementary treatment, you just do not so easily notice it since these fields try to use abstract methods. Let us assume you get it published. This is as hard or harder than to solve the problem, though not intensive work.
You will not get any natural publicity to the paper from the press. The experts will not answer to emails. They will try to make a smear campaign. As an example, google: “Supposed proof by Jorma Jormakka of the $1000000 Clay problem” and see that the main opponent cowgod42 was shown wrong in exactly every case and the proof stays, but he still managed to make a smear campaign. Those people are called trolls and they do exist, they are not really students but with a higher education. You see the smear campaing, cranks, crack-pots etc. It is very typical.
As the experts do not want to comment unless they find an error, you have to force them to do so. They do not hesitate to state totally false arguments backed by their authority in order to defame the proof. See the answer by Terry Tao at the end of “Why global regularity for Navier-Stokes is hard”. All his arguments are clearly false (we are talking of a peer-reviewed and many times checked journal paper, you do not crack it so easily, not even Tao) but he tries to do what is called psychological operation, twist everything backways and claim it is so. Probably many will not look at your paper and notice that all the guru said is flatly wrong. From some other top expert, you may get a journal paper review with obvious errors. It is good if you can collect obviously contradictory reviews from several experts – like one says it is obviously unique, another says it is obviously nonunique. Then the ordinary (good) mathematicians are more willing to check the proof. So, they may read it and conclude it is correct. The leading experts will probably never answer at all.
This is the reality. There really is the establishment who will not want to accept your paper, and the large community who does not care, why should they. You want to ask is everything as in the ideal world: if there is a correct solution, people are happy to read it. I can say, no. This is not the case. The situation in science is not different from the situation in the press or in banking, all of these fields have an establishment (related?). As a conclusion, an amateur may find a solution to P versus NP, but he must have powerful friends if the proof is accepted.
Jorma,
I read some of your work on the Navier Stokes problem, claiming that the solution doesn’t have to be unique. Congratulations on this.
I also looked at your paper on the P vs. NP problem with the subset-sum. I found it difficult and didn’t get to finish it. Hopefully, one day I will.
I try to learn from all comments. The last comment on this blog that was made about my paper convinced me that I needed to rewrite some parts of my paper to make things clearer. I hope it will be up on arxiv.org tonight.
You said, “As a conclusion, an amateur may find a solution to P versus NP, but he must have powerful friends if the proof is accepted.” This may be so, but as for the reaction of the math and computer science community to my proof, I can’t change how anyone thinks. In life, results are not what really matter. What matters is that one does his or her best with no regrets.
I agree both with the last sentences of Craig and Jorma.
In the P!=NP paper, do not start from the beginning. Look at Figure 1 and reconstruct the proof in our mind from that, then read the details. You want n/2 subproblems which all must be checked (by an algorithm working in any way, not limiting the algorithm, only offering the algorithm a problem where all n/2 parts must be solved since there is no solution in any of them). Make these problems as in the figure, left side a worst problem of n/2, then n/2 values where any solution must select one. This is n/2f(n/2) computation time. The problem is that the right hand side depends on the sum j. Thus, in the next step in figure 1 fix the lower half bits so tha there are more than n/2 combinations, so it will take longer time by the same argument. Then try to fix the upper half bits. The last step is that any fixed n-tuple is any way faster than the worst. From this just think how to fill in the details, they are all written there.
Actually you can change how people think by making a strategy. I first used an extremely polite approach, only to notice that it does not work. Experts are usually not polite. There is a big risk in adopting an aggressive strategy. Thus, I strongly advise, do not do so if it is the field that you depend for your salary. If it is not, go ahead. This is why amateurs have much less risk than professionals. Additionally the professionals seem to be super competitive looking for fame. Somebody like me only does this for fun, not so serious, nice to solve problems that you cannot do in the normal work, more like filling a lotto coupong and enjoying it. For them it is very serious competition for the place on the sun.
In my P!=NP proof there is Lemma 1. It may throw some light to why there are so many proof attempts for both P=NP and P!=NP. Usually the subset sum problem is stated without defining the sizes of the numbers. If the numbers grow at most polynomially, there is a polynomial time algorithm (lemma 1). If their bitsize grows faster than any polynomial, there cannot be a polynomial time algorithm since no algorithm can read the input data in polynomial time. Thus, the growth of the bit sizes must be defined. I fixed it to linear growth, as this seems to be what we usually think in the case of the subset sum problem. I do not know if this could be the reason for some of the P=NP proofs, but maybe accepting the used definitions, some of them could be correct, though that does not show P=NP.
Here is perhaps one example of an amateur proposing a closure on the P versus NP debate with a very different approach that uses non-DFS representational scheme. I’m still reeling from the talk I heard from Prof. Narendra Chaudhari on his O(n^13) agorithm for 3SAT problem. Check out the paper published in Journal of Indian Academy of Mathematics at http://dcis.uohyd.ernet.in/~wankarcs//index_files/seminar.htm
I earlier wrote that I have very seldom on my academic caree met actual cranks. Now I must revise the position. There are cranks in the Internet. They are not the amateurs who try to solve the P versus NP problem. Those are nice people who only take part into a contest for a million dollars. Fully understandable. The cranks are the people who without any mathematical background go on arguing against published peer-reviewed journal articles. This I do not understand. They seem to have no confidence on peer-review and they write arguments against a paper totally without thinking. It seems quite useless to answer to them as they have very fixed minds, there is no way to convince them. These cranks defend the established scientific order (no results from outsiders) and use all kind of pseudoarguments: this paper is not written in latex, this paper has too few references, this is too easy, this is too difficult, this author is unknown to us (=the center of the world I guess). These cranks are well supported by the eminent experts. Nobody knows why these people should be experts on the topic since they most likely never made a major attack on the problem (as a top expert would have solved it if he had tried it long enough). However, they are considered eminent and they strongly believe it themselves. These experts do not read a paper. They simply write some standard arguments and reject a paper. I call it arrogance.
There is famous quote of Max Planck:
“A scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die and a new generation grows up that is familiar with it.”
About the quality of reviews in theoretical computer science journals. I just read one purpoted proof of P versus NP that had been rejected by a journal. The review was apparently so bad quality that the author could not see what was wrong in his argument. It took only 10 minutes to read the paper and to write a report that I hope will clearly show the error so that the author understands it. This shows how poor the referees are. They have no personal experience on P versus NP and present generic arguments, which though in a certain sense correct, are not at all helpful to the author. One has to be an expert on the problem, if we are talking of hard problems, in order to be a reviewer. Additionally, one should have enough sense to write sensible reviews. I think the problem of so many unchecked P versus NP proofs is that the field does not fill the standards of good peer-review for these articles. It is a sign of illness on the field.
I got to the max-cut problem by chance, and put practically all my experience with it on http://mkatkov.wordpress.com/
I think I have nothing to add to it, end therefore quitting the enterprise. I’m not planning to publish it.
If you find any useful peace in it feel free to use it in your work, otherwise it is another peace of garbage.
Of cause, if you have any suggestions how to clarify the presentation, or find some weak point that need more attention, I’m ready to help.
All the Best,
Misha
It is time to check a P=NP: Response to Reviewers .
The partition problem asks whether a given sequence
finding min p(x) is equivalent to finding minimum
Sums of squares program (SOS):
For polynomial
Discriminant of (4) with respect to
Since
POSITIVE SEMIDEFINITE DIAGONAL MINUS TAIL FORMS ARE SUMS OF SQUARES. Therefore, SOS converges to global minimum of p.
The geometry of the problem is to find the closest
Did you try plugging this into an SOS solver?
An advice from the great physicist R. Feynman “The first principle is that you must not fool yourself and you are the easiest person to fool.”
http://enimode.com – короткие платья
http://enimode.com – бандажные платья
The following is a quote by Richard Karp, drawn from Bill Gasarch famous P vs NP Poll. I really like it:
He says “young researcher”, however my feeling is that it may turn out to apply as well to an amateur, and for the same reason.
another interesting case study as far as “amateurs” is Balmer, who found the math formula(s) for atomic spectra, a breakthrough that was later incorporated by Bohr into his model of the atom & leading to atomic theory. Balmer was hardly an “amateur” in one sense, having a Phd in mathematics. however, he was not trained/formally educated in physics. accounts of his finding the formula sometimes refer to him as a “swiss schoolteacher”. so he was plausibly an amateur in physics.
so the concept of amateur vs outsider is something to study. there are probably more “outsiders”, in fact many cases of this, making serious contributions to science than amateurs.
this is all glamorized in the fun hollywood movie good will hunting which you may have referenced elsewhere in your blog.
here is an “outsider” attack on P vs NP by a software engineer
Dear Professor, I have “known better” this paper can be the solution of P versus NP:
https://hal.archives-ouvertes.fr/hal-01139624
and pdf in
https://hal.archives-ouvertes.fr/hal-01139624/document
Indeed, in that work I proved that:
$POLYLOGTIME \neq NLOGTIME$
in a trivial way. Next, I proved that:
If $P = NP$, then $POLYLOGTIME = NLOGTIME$.
in a trivial way too. From that result we can see $P \neq NP$.
For that reason I’m quite assure there are big chances that my proof were correct. Certainly, I’m truly convinced, even though I have failed several times with other intents.
Regards..
Oops, you forget that Fermat was an amateur…
Even though most of the community believes P != NP, do researchers still entertain the thought that P = NP? Is it stigmatized to attempt to find an algorithm for an NP-hard problem? This I think would be an amateur’s best bet at answering the question – a nifty algorithm that is simple to understand but clever.
Some have this kind of idea, but no results yet.
http://fexpr.blogspot.fr/2013/07/bypassing-no-go-theorems.html
I’m an amateur mathematician with a graduate education in mathematics. I found a sufficient and necessary condition of a planar graph to be Hamiltonian, and I suppose this is a new research result and I hope it is correct. A proof can be found here:
http://www.bookofproofs.org/branches/characterization-of-planar-hamiltonian-graphs/
Since the (planar) Hamiltonian problem is NP-hard, my sufficient condition leads to another NP-hard problem but this comment field is too short to explain it here. Provided my result is correct, maybe there is another amateur mathematician who can find a P-time algorithm for finding my sufficient condition 🙂
Dear Andreas
It appears that your result is quite interesting and sound. Similar result has been obtained in my arxiv paper in 2009 on the algorithmic proof of Barnette’s Conjecture. I extract the abstract here:
In this paper we have given an algorithmic proof of an long standing Barnette’s conjecture (1969) that every 3-connected bipartite cubic planar graph is hamiltonian. Our method is quite different than the known approaches and it rely on the operation of opening disjoint chambers, bu using spiral-chain like movement of the outer-cycle elastic-sticky edges of the cubic planar graph. In fact we have shown that in hamiltonicity of Barnette graph a single-chamber or double-chamber with a bridge face is enough to transform the problem into finding specific hamiltonian path in the cubic bipartite graph reduced. In the last part of the paper we have demonstrated that, if the given cubic planar graph is non-hamiltonian then the algorithm which constructs spiral-chain (or double-spiral chain) like chamber shows that except one vertex there exists (n-1)-vertex cycle.
Combining these results may lead to an efficient solution of Hamiltonian cycle problem in planar graphs.
My arxiv paper is here:
https://arxiv.org/abs/0904.3431
Dear Ibrahim,
thanks for taking the time to comment on my guest post.
I understand that your CCP algorithm for 3-connected bipartite
planar graphs is a polynomial algorithm to find, what I call the minimal tree decomposition of the dual graph of a given planar graph, for which we want to find the Hamiltonian cycle, if it exists.
Note that being biconnected is an obvious necessary condition for a planar graph to be Hamiltonian (otherwise the graph would have at least one cut vertex and would be non-Hamiltonian). Thus, when trying to solve the general Hamiltonian cycle problem for planar graphs, we can focus on biconnected planar graphs.
What would be the obstacles (if any) to apply your polynomial-time CCP algorithm on general biconnected planar graphs?
Quick answer to your question. We don’t know exactly which sub-sets of the entrances (door-edges) lead to Hamiltonian cycle and your result would be useful in this direction.
Ok, have you performed a run-time analysis of your CCP algorithm, if trying out all entrances?
Moreover, you are talking in your paper about “spiral chains”, (i.e. path structures in my dual planar graph). In my result, I only managed to prove those structures to be trees in general case (and not paths – which could prove to be a special case only). Is there any compelling reason you have found for these structures (i.e. your “spiral chains”) to be a paths in the dual graph instead of trees? If there is such a reason, this would significantly reduce the search space, if we tried to construct the most efficient algorithm to find them.
No detailed analysis performed. In your example, the tree decomposition is in fact double-spiral chain (bold black and dashed bold black edges). See also hamiltonian cycle in my paper (Fig. 5) which is double-spiral chain with two entrance doors of web 10_4 graph.
Maybe these are in fact path structures, I neither have found any counter example, nor have I managed to prove the opposite. A proof of this conjecture would be on itself an interesting question.
I’ve just glanced through your blog post discussing Ramanujan – plan to read in in detail and as well to go through the many responses. I believe it would have been ‘better’ to refer to GH Hardy as exactly that and not as “Godfrey Hardy”. Just my personal opinion.
P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed.
I show a solution to that problem as follows:
Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n – 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.
You could read the details in the link below…
https://hal.archives-ouvertes.fr/hal-01509423/document
A video in youtube with the explanation of my P versus NP solution!!!
https://youtu.be/40C40QCZRg0
Hi!!! I tried to prove: P=NP⇒∃k∈N:TIME(n^{k/2})=NTIME(n^{k/2}). However, I intended to demonstrate that ∀k∈N:TIME(n^{k/2})≠NTIME(n^{k/2}). In this way, I showed that P≠NP. I think my proof could be easy to understand. I submitted to a journal and I received the following answer:
“Mistakes exist in the classes definition and the main argument. Please note also that many reviewers nowadays refuse reading papers about claims of P vs NP. We suggest that you first speak to some complexity experts (e.g. in your references) about your “proof” and/or publicize your “claims” via a web site.”
So that was what I done. I put the proof in a preprint website and you could access here:
https://hal.archives-ouvertes.fr/hal-01533051/document
I’m really interested in improve the proof. I think those mistakes can be fixed. Let me know in the following email if you are interested in improve this paper together and participate as a co-author:
frank.vega@yahoo.com
Best….
Hi,
Developed an algorithm that is constructive, usable, complete exhaustive search. Time complexity is better than quasi-polynomial time where n is up to few 1000(s) and slower than quasi-polynomial time when n is above few 1000(s). Space complexity is O(n^3).
Slides can be found at Slides(pdf) and Slides(tex)
Working implementation of algorithm in C++ can be found at github
Thanks
The answer of p versus np 0 f(x) because n = 0 and p = f (x). I have to get $1 million from 1 company or I am telling everyone this problem and everyone will know. I am a genius buy I don’t get it why no one gets money from it.
As a follow up on Personne comment in response to Craig (https://rjlipton.wordpress.com/2010/07/01/can-amateurs-solve-pnp/#comment-3875), when he says:
“[…] Then, you have to conclude that an algorithm exists which solves subset-sum in time O(2^n/4) up to a polynomial factor -even if you don’t happen to know this algorithm.”
I confirm such algorithm exists, (deterministic and exact)
The algorithm operates on O(N*2^MIN(N,W)/4) where N is the number of elements and W is Log2(max(set values)).
(This runtime is both for ‘yes’ and ‘no’ and output the solutions)
I found a method to solve an NP-complete problem in polynomial time. My scheme differs from a kind of to search method entirely, and no related researchers in resent study.
I wrote down the proof neatly as I was possible. But I am an armature in this field. Therefore, I thought my writing should be some flaw that some researchers believe to give up reading. I want to a consultant to avoid such a case.
I already have consulted several researchers. Many of them only ignored.
Then, I submitted some international conferences. Some reviewers recommended submitting to top international conferences or a journal after writing to the full paper. Because there may be people, who can review this type of paper.
But I don’t know how to write a full paper. I consult to an expert.
When I attended a workshop, I introduced my thought. One of researcher said to me.
“P=NP is synonymous with making a permanent institution. If your claim is right, the world will overturn. Therefore your idea is too difficult to accept them. If your method is conditional, it may have been easy to accept.”
I am really in trouble for reaching some experts to consult in this problem. If someone knows how to contact an expert, please suggest me.
In 1973, Larry J. Stockmeyer and Albert R. Meyer proved that the problem SIMULTANEOUS INCONGRUENCES is NP-complete with a transformation from 3SAT. In December 2017, a proof showed IF the following problem:
Definition 1: OTHER–3SAT
INSTANCE: A Boolean formula in 3CNF and a satisfying truth assignment.
QUESTION: Has this formula another satisfying truth assignment?
Could be reduced in polynomial time to the another problem:
Definition 2: OTHER–SIMULTANEOUS INCONGRUENCES
INSTANCE: An instance of SIMULTANEOUS INCONGRUENCES and a certificate x.
QUESTION: Is there an integer y which is a certificate different of x?
THEN P = NP. The question would be:
Could any Theoretical Computer scientist prove that P = NP using this argument?
In 1978, Kenneth L. Manders and Leonard Adleman proved that the problem Quadratic Congruences is NP-complete too. In December 2017, on the same proof is shown this problem can be solved in polynomial time for the average case. The other question which immediately appears would be:
Could this problem may still be solved totally efficient considering “most” of the polynomial time inputs that occur in practice just ignoring those inefficient “small” number of inputs or maybe find a method to relate the two?
The detailed proof will be available in the HAL preprint soon:
https://hal.archives-ouvertes.fr/hal-01665674/document
But now is only available in
https://www.academia.edu/35444792/P_versus_NP_on_NP-completeness
https://figshare.com/articles/P_versus_NP_on_NP-completeness/5709676
This study about some properties of the class NP–complete might address to think in the possibility of a P = NP answer. However, the paper does not explicitly conclude with an answer of the P versus NP problem. Scott Aaronson predicted that a serious P = NP approach would certainly unveil several other questions that are still unresolved. For that reason, we think some speculative proofs derived from this paper in the future might help to contribute to the field of Computer Science and many other fields in case of being correct. Would you dare to try…?
I decided to make the polynomial time reduction by myself and therefore P = NP.
The detailed proof will be available in the HAL preprint soon:
https://hal.archives-ouvertes.fr/hal-01665862/document
But now is only available in
https://www.academia.edu/35449427/The_P_NP_Answer
https://figshare.com/articles/The_P_NP_Answer/5709829
I hope this could help in some way…
My article “Quadratic Congruences on Average Case” solves an NP-complete problem in average case. It is true that Hamilton cycle and some others could be solved in average case over inputs. However, my algorithm (in the same way as Quicksort) is polynomial for a large amount of inputs (because the infinite set of elements that cannot be solved in polynomial time is infinitesimal when the numbers of inputs tend to infinity). The preprints are in
https://www.academia.edu/35493255/Quadratic_Congruences_on_Average_Case
Or
https://figshare.com/articles/On_Average_Case/5729538
I hope this can help…
A series of numerical searches for counterexamples to Beal’s conjecture has excluded all possible solutions having each of x, y, z = 7 and each of A, B, C = 250,000, as well as possible solutions having each of x, y, z = 100 and each of A, B, C = 10,000. I proved we will fail in the prolonged search of counterexamples since the Beal’s conjecture is true. You could see the proof in
https://www.academia.edu/35712647/The_Beals_Conjecture_Answer
Or
https://figshare.com/articles/The_Beal_s_Conjecture_Answer/5807385
I hope this can help in some way…
Sharp-P = P is a fundamental question that it is as important as it is unresolved. We already know that P is not equal to EXP. We prove if Sharp-P = P, then we can determine in polynomial time which subsets could be solved in a feasible polynomial time from every EXP language. This result conclude with an interesting consequence in case of P = #P, which might help us to solve the P versus #P problem. You could see the proof in
https://www.academia.edu/35878963/The_P_Sharp-P_Consequence
Or
https://figshare.com/articles/The_P_Sharp-P_Consequence/5873595
I hope this can help in some way…
I have made important changes improving my P versus NP and Beal’s conjecture proof…
You could see the proof of P versus NP in
https://www.academia.edu/35449427/The_P_NP_Answer
Or
https://figshare.com/articles/The_P_NP_Answer/5709829
And you could see the proof of Beal’s conjecture in
https://www.academia.edu/35712647/The_Beals_Conjecture_Answer
Or
https://figshare.com/articles/The_Beal_s_Conjecture_Answer/5807385
I hope this can help in some way…
I have found the other proofs that put here are not relevant at all or the proofs are incorrect.
Now, I am only sure of these two results
The P versus NP proof:
https://www.academia.edu/35449427/The_P_NP_Answer
And the average case proof:
https://www.academia.edu/35493255/Quadratic_Congruences_on_Average_Case
I have made several updates in my profile of these papers (where are other papers too):
https://uh-cu.academia.edu/FrankVega
and I hope this could actually really help in some way…
After a revision of my paper about P versus NP, I decided to fix some details and change the title of the paper. Since the site of Academia change the web URI according to the tittle, then here I send you the new link of my paper about this problem
https://www.academia.edu/35949519/P_versus_NP
And I also make changes as I already mentioned in
https://www.academia.edu/35493255/Quadratic_Congruences_on_Average_Case
I feel pretty sure about these two results. The one with the answer of P versus NP problem (affirming that P = NP with a polynomial time algorithm) and the second one with the average case of the NP-complete problem Quadratic Congruences (which may be so feasible as the average case of Quicksort).
I really hope my work can help in some way(I really wish it…) and I will expect for a positive answer from a journal this time. Thank you for sharing my comments. Since I have not paid for my work, I believe these comments are suitable for this post because I might be considered as an amateur due to that reason and even though my work could be correct or not, maybe these ideas could help to find a definitely solution in the same way these amateurs, that were mentioned here, did in their times.
I have made substantial changes in my paper P versus NP. See more in…
https://www.academia.edu/35949519/P_versus_NP
I hope this can help in some way…
as
Hi dedusuiu,
I just added the following fragment in my preprint of P versus NP solution:
“Since $|x| + |b_{1}| + |b_{2}| + \ldots + |b_{n}|$ is polynomially bounded by the instance (where $|\ldots|$ denotes the bit-length function), then this new solution could also be accepted if this string complies with the limit according to the problem $SI$ within the certificate’s length boundary as $NP$ problem otherwise we can try with the another solution $x – b_{1} \times b_{2} \times \ldots \times b_{n}$ that would be a certificate in case of $x + b_{1} \times b_{2} \times \ldots \times b_{n}$ were not.”
The problem is when $x + b_{1} \times b_{2} \times \ldots \times b_{n}$ is not a certificate because it is too large, then $x – b_{1} \times b_{2} \times \ldots \times b_{n}$ will certainly be…
I did not add this detail in my previous submission to a journal for which I’m waiting an aswer, so this is something I should fix in some revision. The version with the problem fixed is in:
https://www.academia.edu/35949519/P_versus_NP
At the same time, I am just squeezing my mind trying to figure out why I received this response from a journal for the another paper on average case analysis:
“I have quickly reviewed your paper and found a flaw in your average-case analysis. Your argument is that since for a (1-\epsilon) fraction of numbers at most n, the running time of the algorithm is polynomial, the average-case running time is polynomial. The argument is not correct since (\epsilon * exponential) + (1 -\epsilon) * polynomial is exponential. Note, also, that the polynomial changes (i.e., the constant attached to lnln(n) that serves as an upper bound on the number of different prime factors of n increases) as \epsilon decreases.”
Maybe I am too dumb or maybe they review too quickly that they do not understand the definition of Normal Order. That’s why I added the fragments that are in quotes in the definition of Normal Order so maybe another journal could accept the paper:
“We shall say, roughly, that a function $f(n)$ has the Normal Order $F(n)$ if $f(n)$ is approximately $F(N)$ for almost all values of $n$. More precisely, suppose that “$F(n)$ complies with”
[(1- \epsilon) \times F(n) < f(n) < (1 + \epsilon) \times F(n)]
for every positive constant $\epsilon$ "that we might choose" and almost all values of $n$."
Actually that above definition is not mine and is wide known in Number Theory (they do not understand that $\epsilon$ must be a constant and could be any value such as $\frac{1}{10^{999999999999999999999999999999}}$)… Who knows maybe it could happen the same with my P versus NP solution…”””shit happens (I'm preparing for the worst ;)…)”””… however you can still see the preprint from the average analysis here:
https://www.academia.edu/35493255/Quadratic_Congruences_on_Average_Case
Actually my argument in average case analysis is based on the Hardy–Ramanujan theorem that you could find here:
https://en.wikipedia.org/wiki/Normal_order_of_an_arithmetic_function
Hello fellows,
I have already proved a solution to the Beal’s conjecture showing that is indeed true and thus we conclude announcing the failure in the prolonged search of counterexamples. The preprint paper is in
https://www.academia.edu/36258783/Beals_conjecture
and
https://figshare.com/articles/The_Beal_s_Conjecture_Answer/5807385
I hope this can help in some way…
My whole valid contribution in trying to approach to the P versus NP problem:
https://figshare.com/articles/Quadratic_Congruences_on_Average_Case/6118847
https://figshare.com/articles/The_complexity_of_class_OTHER-NP/6118841
https://figshare.com/articles/The_complexity_of_class_TAUTOLOGY-NP/6118844
I hope this might help us in some way…
I have shared my whole last valid contribution in Academia:
The complexity of class TAUTOLOGY-NP
https://www.academia.edu/36421545/The_complexity_of_class_TAUTOLOGY-NP
The complexity of class OTHER-NP
https://www.academia.edu/36421546/The_complexity_of_class_OTHER-NP
Quadratic Congruences on Average Case
https://www.academia.edu/36421543/Quadratic_Congruences_on_Average_Case
I hope this might help us in some way…
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. TAUTOLOGY-L is a problem of deciding given an instance x of a language L whether every possible appropriate answer for x is actually a solution in L. The class TAUTOLOGY-NP contains those languages TAUTOLOGY-L where L is in NP. Another major complexity class is NP-complete. To attack the P versus NP question the concept of NP-completeness has been very useful. We define the completeness of TAUTOLOGY-NP using the polynomial time reduction as well. We show TAUTOLOGY-SAT is complete for TAUTOLOGY-NP. However, the complement of TAUTOLOGY-SAT is a well known NP-complete problem. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. Therefore, if every TAUTOLOGY-NP language is in P, then P = NP. We demonstrate there is a TAUTOLOGY-L language that is not only complete for TAUTOLOGY-NP, but it is also in P. In this way, we demonstrate the P versus NP problem.
https://www.academia.edu/36428710/P_versus_NP
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is Sharp-P. Whether P = Sharp-P is another fundamental question that it is as important as it is unresolved. If any single Sharp-P-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. The problem Sharp-MONOTONE-2SAT is known to be Sharp-P-complete. We prove Sharp-MONOTONE-2SAT is in P. In this way, we demonstrate the P versus NP problem.
https://figshare.com/articles/P_versus_NP/6159857
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. We show some results based on this problem and the properties of congruences: first, the Quadratic Congruences, which is known to be NP-complete problem, could be solved in polynomial time for the average case; next, from a complexity class that we call OTHER-NP could be proved P = NP over polynomial reductions from some languages in OTHER-NP; finally, the problem Sharp-MONOTONE-2SAT, which is known to be Sharp-P-complete, is in P. In this way, we demonstrate the P versus NP problem.
https://www.academia.edu/36507664/The_Complexity_of_Congruences
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is Sharp-P. Whether P = Sharp-P is another fundamental question that it is as important as it is unresolved. If any single Sharp-P-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. The problem Sharp-MONOTONE-2SAT is known to be Sharp-P-complete. We prove Sharp-MONOTONE-2SAT is in P. In this way, we demonstrate the P versus NP problem.
https://www.academia.edu/36428710/P_versus_NP
I have found the following counterexample for Beal’s conjecture:
1054962892930838144552824032072744^3 + 2^336 = 3^212
You could see more in:
https://www.academia.edu/36557701/Counterexample_for_Beals_Conjecture
After be put on hold for several days, my article is now available at:
http://arxiv.org/abs/1805.01755
Two theorems about the P versus NP problem be proved in this article (1) There exists a language L, that the statement L∈P is independent of ZFC. (2) There exists a language L∈NP, for any polynomial time deterministic Turing machine M, we cannot prove L is decidable on M.
The original full version article in my personal blog:
https://tianhengtsui.wordpress.com/
My following paper has gained too much attention in Academia.edu preprint server. It is right now one of the top papers of this site. Perhaps this is a good approach to a final solution: who knows? This is the Abstract and the URL link:
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is Sharp-P. Whether P = Sharp-P is another fundamental question that it is as important as it is unresolved. If any single Sharp-P-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. The problem Sharp-MONOTONE-2SAT is known to be Sharp-P-complete. We prove Sharp-MONOTONE-2SAT is in P. In this way, we demonstrate the P versus NP problem.
https://www.academia.edu/36428710/P_versus_NP
The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. On the other hand, P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? We will define as the strongest Goldbach conjecture when every even integer greater than 6 can be written as the sum of two different primes. We prove if P = NP, then the strongest Goldbach conjecture is false.
https://www.academia.edu/36656892/The_Goldbachs_Conjecture_when_P_NP
The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. On the other hand, P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? We will define as the strongest Goldbach conjecture when every even integer greater than 6 can be written as the sum of two different primes. We prove if P = NP, then the strongest Goldbach conjecture is false.
https://www.academia.edu/36656892/Strongest_Goldbach_conjecture
The Riemann hypothesis is considered as one of the most important conjectures in Mathematics. This consists in knowing whether the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 0.5. This conjecture was proposed by Bernhard Riemann in 1859. Since that date, several mathematicians have addressed the Riemann hypothesis, but none of their attempts have yet been accepted as correct solutions. On the other hand, P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? We prove if P = NP, then the Riemann hypothesis is false.
https://figshare.com/articles/Riemann_hypothesis/6374723
The Riemann hypothesis is considered as one of the most important conjectures in Mathematics. This consists in knowing whether the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 0.5. This conjecture was proposed by Bernhard Riemann in 1859. Since that date, several mathematicians have addressed the Riemann hypothesis, but none of their attempts have yet been accepted as correct solutions. On the other hand, P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? We prove if P = NP, then the Riemann hypothesis is false.
https://www.academia.edu/36730663/Riemann_hypothesis
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a 1,000,000 prize for the first correct solution. This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is Sharp-P. Whether P = Sharp-P is another fundamental question that it is as important as it is unresolved. If any single Sharp-P-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. Given an undirected graph G=(V, E), Sharp-NON-CLIQUE is the problem of counting the amount of nonempty subsets from V such that each set is not a clique. We show the problem Sharp-NON-CLIQUE is Sharp-P-complete. We prove Sharp-NON-CLIQUE is in P. In this way, we demonstrate the P versus NP problem.
https://figshare.com/articles/P_vs_NP/6406145
https://www.academia.edu/36761366/P_vs_NP
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute. This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. To attack the P versus NP question the concept of NP-completeness has been very useful. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. MONOTONE 3SAT is a known NP-complete problem. We prove MONOTONE 3SAT is in P. In this way, we demonstrate the P versus NP problem.
https://zenodo.org/record/1285952#.WxrPnJ9KjIV
https://www.academia.edu/36807369/P_vs_NP
https://figshare.com/articles/P_vs_NP/6406145/6
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute. This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. To attack the P versus NP question the concept of NP-completeness has been very useful. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. MONOTONE 3SAT is a known NP-complete problem. We prove MONOTONE 3SAT is in P. In this way, we demonstrate the P versus NP problem.
https://zenodo.org/record/1285952#.WxrPnJ9KjIV
https://www.academia.edu/36807369/P_vs_NP
https://figshare.com/articles/P_vs_NP/6406145
There is a newest version in:
https://zenodo.org/record/1286204
https://www.academia.edu/36807369/P_vs_NP
https://figshare.com/articles/P_vs_NP/6406145
P versus NP
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute. This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. To attack the P versus NP question the concept of NP-completeness has been very useful. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. Quadratic Congruences is a known NP-complete problem. We prove Quadratic Congruences is in P. In this way, we demonstrate the P versus NP problem.
Proposal submitted to Information Processing Letters and Highlights 2018…
https://zenodo.org/record/1287288
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity classes are LOGSPACE and NLOGSPACE. Whether LOGSPACE = NLOGSPACE is another fundamental question that it is as important as it is unresolved. SAT is easier if the number of literals in a clause is limited to at most 2, in which case the problem is called 2SAT. This problem can be solved in polynomial time, and in fact is complete for the complexity class NLOGSPACE. If additionally all OR operations in literals are changed to XOR operations, the result is called exclusive-or 2-satisfiability, which is a problem complete for the complexity class LOGSPACE. Given an instance of exclusive-or 2-satisfiability and a positive integer K, the problem maximum exclusive-or 2-satisfiability consists in deciding whether this Boolean formula has a truth assignment with at leat K satisfiable clauses. We prove that maximum exclusive-or 2-satisfiability is in NLOGSPACE. Moreover, we demonstrate this problem is NP-complete. To attack the P versus NP question the concept of NP-completeness has been very useful. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. Since every language in the class NLOGSPACE is in P, then we show that our problem is in P and NP-complete and thus, P = NP.
https://zenodo.org/record/1297654
https://www.academia.edu/36915996/P_versus_NP
Given an instance of $\textit{XOR 2SAT}$ and a positive integer $2^{K}$, the problem exponential exclusive-or 2-satisfiability consists in deciding whether this Boolean formula has a truth assignment with at leat $K$ satisfiable clauses. We prove exponential exclusive-or 2-satisfiability is in $QP$ and $\textit{NP-complete}$. In this way, we show $QP \subseteq NP$.
https://zenodo.org/record/1306965
https://www.academia.edu/36993851/QP_versus_NP
It was updated in
https://zenodo.org/record/1306970
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? We define a coding to be a mapping from symbols of some alphabet (not necessarily one-to-one). NP is closed under codings. However, P is closed under codings if and only if P = NP. We show a coding of a defined NP language which derivate in a NEXP-hard problem. If we assume that P = NP, then this NEXP-hard language would be in P since P would be closed under codings. Nevertheless, this is not possible due to the Hierarchy Theorem. Thus, we obtain a contradiction taking as assumption that P = NP. In this way, we prove P is not equal to NP by reduction ad absurdum.
You can view the proof in
https://www.academia.edu/37055793/P_vs_NP
and download it in
https://zenodo.org/record/1312908
Hi Frank, you are quite active in this field and this blog. I noticed that you posted a proof for P equals NP on June 25, 2018 and a proof for P does not equal NP on July 16, 2018, did you?
A researcher which I have communication found flaws in the proof on June 25, so I tried to face the problem in a different approach. I finally made a final solution and I will submit it to a journal after revising with that researcher which is a kind of mentor I think. The purpose of the preprint and the sharing in this site is to allow me to discuss this topic with new people interested in this topic and let them know what am I doing about it. This post is about amateurs, and in this way, I am an amateur trying to show you amateurs approach to this difficult problem. If you really want to follow what am I doing about it, you could check this last version of the paper in:
https://zenodo.org/record/1317603
and
https://www.academia.edu/37055793/P_versus_NP_under_codings
Thanks in advance…
Rectification: My intention is not to give any credit for people who review my proofs. This would be a lack of respect, since these proof have been not revised by a journal or other peer-review site. The only intention is to share my proofs in order to debate and work about it with anyone interested on them ;).
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. We define a coding to be a mapping from symbols of some alphabet (not necessarily one-to-one). NP is closed under codings. However, P is closed under codings if and only if P = NP. We show a coding of a NP language which produces a NEXP-complete problem when the empty string is considered as a symbol. If P = NP, then this NEXP-complete language would be in P, but this is not possible due to the Hierarchy Theorem. In this way, we prove P is not equal to NP when the empty string is taken as a symbol.
https://zenodo.org/record/1317603
and
https://www.academia.edu/37055793/P_versus_NP_under_codings
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? To attack the P = NP question the concept of NP-completeness is very useful. If any single NP-complete problem is in P, then P = NP. We prove the following problem is in NP-complete and P:
MAXIMUM EXCLUSIVE-OR 2-UNSATISFIABILITY
INSTANCE: A positive integer K and a formula \phi that is an instance of XOR 2SAT.
QUESTION: Is there a truth assignment in \phi such that at most K clauses are unsatisfiable?
Therefore, we demonstrate P = NP.
You can view the proof in
https://www.academia.edu/37150756/P_versus_NP
and download it in
https://zenodo.org/record/1323808
The paper was updated on
https://www.academia.edu/37150756/P_versus_NP
and
https://zenodo.org/record/1323850
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? To attack the P = NP question the concept of NP-completeness is very useful. If any single NP-complete problem is in P, then P = NP. We prove there is a problem in NP-complete and P. Therefore, we demonstrate P = NP.
https://www.academia.edu/37150756/P_versus_NP
https://zenodo.org/record/1344495
See my proof of UP=NP. It is very easy to understand even for non-specialist readers.
https://zenodo.org/record/1419750#.W55I5xnB8ew
You could see my proof of UP=NP in
https://www.academia.edu/37430336/UP_versus_NP
and see my proof of P = NP in
https://www.academia.edu/37431232/Sparse_complete_sets_for_coNP_Solution_of_the_P_versus_NP_problem
You could download them in Zenodo in the respective url:
For UP=NP, we have
https://zenodo.org/record/1419750#.W55I5xnB8ew
For P=NP, we have
https://zenodo.org/record/1420486#.W5_TC9JKjIU
In general, you could see my whole research in
https://uh-cu.academia.edu/FrankVega
Thanks in advance….
See my complete poof of UP = NP on
https://www.academia.edu/37430336/UP_versus_NP
And you download in
https://zenodo.org/record/1433419#.W6eHVRnB8ew
You could see my proof of UP=NP in
https://www.academia.edu/37430336/UP_versus_NP
and see my proof of P = NP in
https://www.academia.edu/37469408/P_versus_NP
You could download them in Zenodo in the respective url:
For UP=NP, we have
https://zenodo.org/record/1434273
For P=NP, we have
https://zenodo.org/record/1434277
In general, you could see my whole research in
https://uh-cu.academia.edu/FrankVega
Thanks in advance….
I think the famous quote by Louis Pasteur is relevant here: Fortune favors the prepared mind.
Hi there. This is an inspiring post. I just finished a P!=NP proof here, it is awaiting moderation on arXiv. I wonder if you would take a look?
https://doesnothavetobeperfect.home.blog/2019/02/09/computation-complexity-and-pnp-proof/
I think it’s not just solving the P vs NP problem. In my paper, I propose a new artificial intelligence test (the Fitzgerald Test), a new computable function (select distinctions) that involves a new architecture. With a little help from Gödel (and Spencer-Brown and Luhmann), we leave behind Turing and von Neumann…
I believe there exist both an insane proof that P≠NP and a galactic polynomial algorithm for SAT. Therefore ZFC is inconsistent but it seems consistent thanks to the limitations of our brain and of our computers.
https://www.reddit.com/r/compsci/comments/augsp7/request_review_for_p_versus_np_paper/
https://www.reddit.com/r/compsci/comments/ax3a75/request_review_for_work_paper_result_p_np/
https://www.reddit.com/r/compsci/comments/ayq5ex/request_review_on_p_versus_np_paper/
Request Review On P versus NP paper
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2588892
New version update(March 10. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2589001
New version update(March 14. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2593729
New version update(March 15. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. To attack the P versus NP problem, the concept of coNP-completeness is very useful. We prove there is a problem in coNP-complete that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2594093
We, the humanity, will solve the big problems…
New version update(March 16. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. To attack the P versus NP problem, the concept of coNP-completeness is very useful. We prove there is a problem in coNP-complete that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2595696
Now I remember that the first time I read about this problem was in the spanish edition of Ian Stewart’s book From here to infinity in 1998. I understood very little, but the title P = NP? caught my attention. In that year, the prize still did not exist…
Last new version update(March 16. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. To attack the P versus NP problem, the concept of coNP-completeness is very useful. We prove there is a problem in coNP-complete that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2596013
Only in 2010, when Perelman rejected the prize, I knew that P=NP? was one of the problems of the millennium. But I was not interested (I’m not a mathematician) until the year 2014…
New version update(March 17. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. To attack the P versus NP problem, the concept of coNP-completeness is very useful. We prove there is a problem in coNP-complete that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2596331
The final update version(March 17. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. To attack the P versus NP problem, the concept of coNP-completeness is very useful. We prove there is a problem in coNP-complete that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2596354
What happened in 2014? A september night I read a note in an Argentine newspaper about P vs NP!!! very well explained by an Argentine mathematician (Adrián Paenza). That same morning I found the solution and sent it to the Institute. Two years later I invented the algorithm. As Ian Stewart says: “Mathematics is not about symbols and calculations. Mathematics is about ideas. In particular it is about the way that different ideas relate to each other. If certain information is known, what else must necessarily follow? The aim of mathematics is to understand such questions by stripping away the inessentials and penetrating to the core of the problem. It is not just a question of getting the right answer; more a matter of understanding why an answer is possible at all, and why it takes the form that it does. Good mathematics has an air of economy and an element of surprise. But, above all, it has significance.”
New update version(March 19. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2597704
Second new update version(March 19. 2019)
P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.
https://zenodo.org/record/2598772
Keith Devlin predicted: “Yet (…) the P versus NP enigma is most likely to be solved by an unknown amateur. In addition to being relatively easy to understand, it is possible that only a good innovative idea is needed to solve it.”
Thanks for the space. Héctor
Dear Hector:
Yes I now recall Devlin’s quote. Thanks for reminding me. I sometimes forget what Ken and I have talked about.
https://rjlipton.wordpress.com/2010/07/01/can-amateurs-solve-pnp/
Here is a quote from the above:
In his third chapter, on the P=NP question, Devlin states that perhaps this problem is one that could be solved by an amateur. I have heard this claim before, and I have mixed feelings about it. Of course we cannot predict who will solve any open problem, and that includes the Millennium problems as well as all other open problems. My mixed feeling comes from saying P=NP could be solved by an amateur seems to mean it is “easier” than the other problems. I do not think this is the case, but ranking the difficulty of open problems is probably impossible.
Best
In my opinion, it’s easy. The complicated thing is that a machine can do it.
Greetings
Result that parity L is equal to L.
https://www.academia.edu/39345145/The_complexity_of_class_L
Result that P is equal to NP.
https://www.academia.edu/39345182/The_P_versus_NP_Problem
I forgot that Academia.edu requires authentication for downloading…
If you want to skip this step you could freely download the papers in
a result that parity L is equal to L
https://zenodo.org/record/3237145
and a result that P is equal to NP
https://zenodo.org/record/3237141
Thanks in advance,
Frank
In order to follow the pieces of advice in the post
https://rjlipton.wordpress.com/2019/04/21/pnp-proofs/
I have written a summary explaining the tricks of my proof of P = NP.
Here you are:
“I have a polynomial algorithm for $\textit{MONOTONE 1–IN–3 3SAT}$ that no one has found before: The trick is that I noticed since every variable appears only as positive literals, then we can replace each occurrence of any variable into a single clause by some unique variable. Since this unique variable appears negated once in a clause of two literals and two times as positive literals in a clause of three and two literals respectively, then we can create sets of fewer than three elements assigned to each literal from each clause into a new Boolean formula in $CNF$, such that for every truth assignment in this new Boolean formula the set assigned to the negated literal of some variable is not mutually disjoint with the sets assigned to the two positive literals from this unique variable and thus, we can evaluate either the negated or the positive literal as true. In this way, we can fix those sets with two elements and guarantee the sets assigned to the literals of each clause are not mutually disjoint. After that, we could reduce to the polynomial problem $\textit{2SET PACKING}$, because exactly one literal will be true from a clause of two literals allowing the appropriated assignment for the variables which appear in the original Boolean formula in $3CNF$ from $\textit{MONOTONE 1–IN–3 3SAT}$ since we must choose exactly one set assigned to the literals of a clause of two literals and exactly one true literal in the clause of three literals which is the clear evidence that the original Boolean formula is indeed an element of $\textit{MONOTONE 1–IN–3 3SAT}$ since we must choose exactly one set assigned to the literals of a clause of three literals. We could this since we require there should be $m’$ mutually disjoint sets where $m’$ is the total amount of clauses in the new Boolean formula in $CNF$ where it is replaced the occurrence of every variable from each clause in the original formula in $3CNF$ by a unique new variable. Notice that we use graphs to represent these both steps in the Figures \ref{figure1} and \ref{figure2}, but this proof has nothing in common with the graph theory.”
You could find this paragraph formatted in the Summary section in the preprint
https://zenodo.org/record/3239377
Thank in advance,
Best regards,
Frank
Following the advice of
https://rjlipton.wordpress.com/2019/04/21/pnp-proofs/
we continue improving the summary for the exact explanation as follows
(
you can download this improvement in
https://zenodo.org/record/3239560
)
“I have a polynomial algorithm for $\textit{MONOTONE 1–IN–3 3SAT}$
that no one has found before: The trick is that I noticed given an
instance $\phi$ of the language $\textit{MONOTONE 1–IN–3 3SAT}$,
then we can construct a Boolean formula $\phi’$ in $CNF$ such that
— If $\phi’$ has a truth assignment with exactly one true literal
for each clause, then $\phi$ complies with the same property.
— $\phi’$ contains the clauses of $\phi$ but modified and there
are at most two clauses of two literals for each occurrence of a
literal from every clause in $\phi$. In this way, there are at most
polynomially number of clauses in $\phi’$ in relation to $\phi$.
— We replace each occurrence of any variable into a single clause
in $\phi$ by some unique variable in $\phi’$ which appears in $\phi’$
as follows: Once negated in a clause of two literals and twice as a
positive literal in a clause of two and three literals when the
variable occurrences appear more than once in $\phi$.
We create sets of fewer than three elements assigned to each literal
from every clause into $\phi’$, such that the set assigned to the
negated literal of some variable is not mutually disjoint with the
sets assigned to the two positive literals from this unique variable
in $\phi’$. Moreover, we modify those sets with exactly two elements
just adding a common element to the sets of the literals of every
clause in $\phi’$, because this guarantee that the sets assigned to
the literals of each clause are not mutually disjoint. The amount of
sets in this procedure is small since there are exactly the same
amount of sets which is equal to the total number of literals for each
clause in $\phi’$. In this way, a truth assignment $T$ for the Boolean
formula $\phi’$ of $m’$ clauses with exactly one true literal for each
clause corresponds to $m’$ mutually disjoint sets assigned for the
literals that were true in this assignment, that is the negated or
positive literal when the variable in $T$ is false or true
respectively. Certainly, the possibility between $m’$ mutually
disjoint sets when every clause of two literals has exactly one set
chosen from its literals makes possible the appropriated assignment of
all the variables in $\phi$ where they were replaced by several unique
variables in $\phi’$ when we evaluate as true each literal which has
been assigned from every selected set. At the same time, we obtain the
property between $m’$ mutually disjoint sets when every clause of
three literals has exactly one set chosen from its literals converts
this into a certificate for the clauses of three literals in $\phi$
which are equivalent to the modified clauses of three literals that
contain $\phi’$ when we evaluate as true each literal which has been
assigned from every selected set. In this way, the collection of these
sets is an instance of the polynomial language $\textit{2SET PACKING}$
assuming that we require $m’$ mutually disjoint sets. If we cannot
pick $m’$ mutually disjoint sets from this collection, then this will
imply $\phi’$ has not a truth assignment with exactly one true literal
for each clause. The reason is because if we cannot choose a single
set for every clause, then there is not a truth assignment where we
may select as true exactly one literal for each clause in $\phi’$. In
addition, we cannot obtain $m’$ mutually disjoint sets where there is
a literal and its negation within the selected sets since as we
explained above those assigned sets are not mutually disjoint.”
Thanks in advance,
https://www.reddit.com/r/compsci/comments/bzeaax/detailed_proof_of_p_np/
https://www.reddit.com/r/compsci/comments/c1xgpo/solution_for_two_major_unsolved_problems_in/
https://www.reddit.com/r/compsci/comments/c4dqh4/solution_of_two_unsolved_problems_in_complexity/
Solution of the P versus NP Problem,
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is coRP. Whether NP = coRP is another fundamental question that it is as important as it is unresolved. It is known when P is not equal to NP, then NP is not equal to coRP as well. To attack the P versus NP problem, the NP-completeness is a useful concept. We prove there is an NP-complete problem in coRP. In this way, we obtain that NP is indeed equal to coRP. Consequently, by contraposition we demonstrate the complexity class P is equal to NP.
https://www.academia.edu/39721020/Solution_of_the_P_versus_NP_Problem
Comments are welcome,
Thanks in advance!!!
https://www.reddit.com/r/compsci/comments/c7lixy/nonconstructive_proof_of_p_np/
https://www.reddit.com/r/compsci/comments/ca3bzc/interesting_result/
P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. NP is the complexity class of languages defined by polynomial time verifiers M such that when the input is an element of the language with its certificate, then M outputs a string which belongs to a single language in P. Another major complexity classes are L and NL. The certificate-based definition of NL is based on logarithmic space Turing machine with an additional special read-once input tape: This is called a logarithmic space verifier. NL is the complexity class of languages defined by logarithmic space verifiers M such that when the input is an element of the language with its certificate, then M outputs 1. To attack the P versus NP problem, the NP-completeness is a useful concept. We demonstrate there is an NP-complete language defined by a logarithmic space verifier M such that when the input is an element of the language with its certificate, then M outputs a string which belongs to a single language in L.
https://zenodo.org/record/3355777
https://www.reddit.com/r/compsci/comments/ck16yi/logarithmic_space_verifiers_on_npcomplete/
I claim a proof that P=NP implies that my algorithm is polynomial and solves an NP-complete problem. I am an amateur in the sense that I have no degree (but I did study math for a few years):
https://math.portonvictor.org/2021/04/08/my-algorithm-that-is-np-complete-in-the-case-if-pnp/
Please check for errors (that’s the third revision of the algorithms, I much hope it’s bug-free). Just 3 pages (the algorithm itself and the proof fits one page).
I was an experienced amateur general topologist and (apparently) solved constructivity of P=NP in about two days since I started to solve a TCS problem.
No, I didn’t broke BitCoin, the algorithm is not efficient.