20 ms·

P = NP Proofs: Advice to claimers

153 points by furcyd 8y ago

vortico 8y ago
By the name, I was expecting this article to be much more technical, giving examples of common errors made by attempted proofs or reasons why certain cruxes in possible proofs would be difficult to overcome.
- kkylin 8y ago
  So was I, something more like this: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.3404&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.... Still, I thought it was a nice post.
w8rbt 8y ago
Very smart people have tried for a very long time to show one way or the other. We don't know if P = NP (seems unlikely) or if P != NP (seems likely). But there is no proof either way. If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Again, this seems very unlikely.
- tyilo 8y ago
  You assume that the proof for P = NP would be constructive.
  - pascal_cuoq 8y ago
    It's automatically constructive. Algorithms can be enumerated. Proofs can be enumerated. For any formalized problem Q in NP, you can always simply enumerate algorithms A and candidate proofs P until you stumble on a pair (A, P) where P is a proof that A answers Q in polynomial time. If P=NP, this first step takes constant time (long but independent on the input). If P!=NP, this first step takes forever. In other words, if you have a non-constructive proof that P=NP, just make “search for the polynomial algorithm” the first step of the algorithm, and now you have a constructive proof.
    - saagarjha 8y ago
      > Algorithms can be enumerated. Proofs can be enumerated. How exactly do you do this?
      - jcranmer 8y ago
        Checking whether a string is a valid proof can be done in polynomial time. So, enumerate all possible strings, and check if each string is a valid proof of what you're trying to find.
        saagarjha 8y ago
        But enumerating all the possible strings takes infinite time? Or, wait, is this saying that since there is some algorithm you can spend some constant amount of time to find it that doesn’t affect the time complexity of your algorithm? I’m not sure I’d call that “constructive”.
        jcranmer 8y ago
        If you know that such a proof exists, then it's guaranteed to terminate.
        kd0amg 8y ago
        is this saying that since there is some algorithm you can spend some constant amount of time to find it Yes. I’m not sure I’d call that “constructive”. The method for constructing the algorithm is given!
        andrewla 8y ago
        > Checking whether a string is a valid proof can be done in polynomial time. That's not true. Curry-Howard says that determining if a proof is correct has the same complexity as programs in general. Even if P=NP, there are still complexity classes strictly larger than P; say EXP, that would result in a proof requiring exponential time to check for validity. That's assuming that "validity" here means true/false-ness, rather than syntactical validity, which is much less useful.
- andrewla 8y ago
  > If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Knuth himself, for example, has casually expressed the opinion (not a proof) that P=NP in the past. When you say "as easily" it belies the nature of polynomial time questions. If it turns out that we can produce an algorithm for 3SAT that is O(n^1e72), then that will in fact prove that P=NP. But this does not make any practical problems "easy".
  - CJefferson 8y ago
    No need for n^1e72, a SAT instance with a couple of hundred variables can usually be solved easily, industrial instances are often hundreds of thousands of variables. Even a O(n^10) algorithm would be of MASSIVE theoretical interest, but almost no practical value.
  - mcguire 8y ago
    https://www.scottaaronson.com/blog/?p=122 https://www.scottaaronson.com/blog/?p=122 See #5. And... https://www.scottaaronson.com/blog/?p=3095 https://www.scottaaronson.com/blog/?p=3095
- jcranmer 8y ago
  I suspect most people, even most computer scientists, have a very limited view of complexity theory. When Big-O notation is introduced, and we discuss algorithms, we tend to only ever come across them in contexts where the algorithm is "small" polynomial or "small" hidden constants are present. How many people can even name a polynomial algorithm that's worse than cubic, or a polynomial algorithm with a massive hidden constant? In practice, these algorithms tend to be hidden in nasty combinatorial problems which sometimes are themselves contrived mainly to force a solution that slow. Yet the evidence suggests that, should P=NP, then the polynomial algorithm is going to be of that nasty combinatorial variety. The main reason for this, informally of course, is that NP-complete problems tend to have their NP-completeness arise from specifically hard instances, rather than generally being hard. SAT is NP-complete, but we can solve many SAT queries we care about (undoing cryptographic algorithms are of course the exception--by design). Graph coloring is NP-complete, except if your graph falls into one of several dozen special cases of graphs which covers most we know about. In other words, there's a kernel of instances where there structure is exponentially complex and there's no way to develop heuristics that are meaningfully simpler than "try every possibility until one works." It is possible that there exists some basis that can describe the complex structure in polynomial terms, but this basis would itself have to embed the complexity we see, and as such, it would be one of those combinatorial monstrosities. Think something of the terms of 3^2^16 as your hidden constant (that's the bounds for the "simple" algorithm in the L=SL paper).
  - ahelwer 8y ago
    Something I've always wondered - if only certain instances of 3SAT are difficult, why are those considered the same problem as easy instances of 3SAT? Why do we say 3SAT is hard, rather than 3SAT with specific structure? Or do we lack the ability to determine whether a given instance of 3SAT is hard?
    - jcranmer 8y ago
      We use the worst-case analysis to drive Big-O notation; if the worst case is hard, then we say the problem itself is hard. This is the main limitation of Big-O, as normally taught: it tends to ignore the practicability of the algorithm for typical cases. Usually, the practice for solving these sorts of problems is to have your algorithm return three values: the solution, unsatisfiable, or timed out. There is literature on how to structure such problems to make it more likely you're going to get answers, but I'm not personally familiar with this area.
throwawaymath 8y ago
On a related note, Scott Aaronson once wrote up a few heuristics he uses to quickly evaluate how likely a P/NP proof is to be incorrect: https://www.scottaaronson.com/blog/?p=458 https://www.scottaaronson.com/blog/?p=458 Aaronson’s rules are more technical than the ones given in this article, the latter of which can be generally applied to most claimed (dis)proofs of famous open problems. In particular, poorly typeset papers from a solo, unknown authors are highly unlikely to be correct when they’re claiming to resolve well known open problems. In regard to the P/NP problem specifically, Aaronson’s examples of weaker open problems which would likely be resolved first - or at least accounted for in some nontrivial way - are analogous to this article’s point about proving weaker theorems first. It would be very suspicious for a proof that P and NP are separable (or not separable) to work at such a high level that it doesn’t prove also new results about the lower bounds of a litany of other problems.
- mormegil 8y ago
  I thought you meant a simpler heuristic http://haspvsnpbeensolved.com/ http://haspvsnpbeensolved.com/ :-)(I had thought Scott Aaronson is somehow connected with it, but probably not, it seems)
  - btrettel 8y ago
    I know the guy who made that website. I think it might have been done at the request of Scott, or Scott advertised it on his blog at some point.
  - pmiller2 8y ago
    That’s kinda funny, but it should at least throw an error when you click the button without providing a URL. :P
  - verma7 8y ago
    I hope to see the day when this website gives the wrong answer.
- neilv 8y ago
  Is all the good math institutionalized now (e.g., you can't do good math without all the benefit of learning background within the institution conventions)? What's the intuition that an extremely important proof will come from someone who gets all the TeX tweaked to camera-ready perfection, goes around and gives the talks, and all the conventional things... rather than a genius out of nowhere who walks into a stranger's office, wordlessly drops on their desk a stack of handwritten pages wrapped in twine, and walks out, never to be seen again? I was thinking of this because I once knew an autistic person, from some humble and isolated upbringing, who was getting some informal math instruction, and they told me they thought they knew a proof for P=NP. I considered it extremely unlikely, but not utterly impossible. (They reportedly tested "off the scale" high in some particular cognitive regard, and I'd noticed a couple minor superpowers.) If that person, to use them as an example, ever actually worked out the proof, and wanted to "turn it in" with their own judgment and access, I wonder where they'd go. And whether it would be somewhere that would take them seriously enough to look at it, and whether they could tell that a proof in unconventional terms had merit. If they get turned away from the first place, would they be discouraged and give up, or would they keep trying, there or elsewhere. If they persisted, would they appear to be a crank because of their persistence and frustration.
ryanstrug 8y ago
P=NP because all inputs and outputs can be represented by a 1’s/0’s number and a line can be drawn between those numbers that’s O(1) and all sets of algorithms are arbitrary so it’s possible to have a set of algorithms that fits the P=NP definition, k thx bye.
- ryanstrug 8y ago
  ‪More specifically algorithms solve arbitrary sets of inputs and outputs. Different algorithms can be aligned with different sets of inputs and outputs that are less natural but within the P=NP criteria.‬
- Chirono 8y ago
  I suspect you're just trolling, but for anyone else: This is true for any bounded input, yes, but doesn't hold for an infinite domain.
deleted 8y ago
[deleted]
AnaniasAnanas 8y ago
Just wondering, why do people not use Coq/Isabelle/Agda/etc in order to check such proofs? Wouldn't that save them from the "shame" of producing yet-another-incorrect P(!)=NP proof?
- throwawaymath 8y ago
  They don't do it because the technology just isn't there yet. Automated theorem checking is typically very difficult for any nontrivial theorem; automated theorem generation is so extraordinarily difficult, it's generally infeasible. The steps to construct a proof of a theorem are as follows: 1. Formally define a language specification which will ostensibly contain the theorem statement and a proof. 2. Search the language space (the set of all strings of the language) for a proof of the theorem statement. 3. If step 2 fails, change the language specification to include prerequisite mathematics or an alternative statement of the theorem. Even when you exploit clever structural properties of the theorem statement and the language definition, it's extremely easy to encounter a combinatorial explosion when you search for a proof. On the other hand, suppose you already have a proof and simply want to verify it using a proof assistant. In order to do so, the language you define must be able to automatically verify all prerequisite mathematics which your proof depends on. Encoding that mathematics into a language is difficult and tedious, and dependency checking is itself vulnerable to combinatorial explosion. It's a very active area of research in its own right, but it can't obviate this problem for the foreseeable future.
  - andrewla 8y ago
    > Automated theorem checking is typically very difficult for any nontrivial theorem I'm not sure this is true -- I thought the whole idea of these theorem systems was to make the kernel of the proof system as simple as possible (to allow a manual proof, or at least high confidence of correctness). If your program can produce an instance of a type, and it type-checks, then it true. Type inference can be tricky, and a lot of what makes the systems usable is the fact that you can omit types and allow the compiler to infer them, but a fully-expressed typed proof outline is enough to quickly verify correctness of the proof.
amiune 8y ago
Why to discourage people to try things with low probability of success? It's hard to find these guys, let them be happy at least for a while
- jerf 8y ago
  You're welcome to try all you want. But after the hundredth crackpot paper someone receives, expect them to be a wee bit less welcoming, open, and excited than they were the first couple of times. I think a lot of people commenting on this topic to this effect are obviously not receiving a huge deluge of crackpot papers. I've never received them myself, but I've seen a couple of instances of people and companies who do, each of them themselves small instances of the problem, and it would have been plenty to try my patience if I had to spend any time at all on each of them.
- rabidrat 8y ago
  I received an email from someone I met recently: > I inted to start doing a project on what causes Parkinson's Desease using Python , Big Data, , Data analyt and Nvidia Supercomputing. You have a skillset that can hel sovle this problem and I coul use your help. If we are successful then we can do the same for other medical deseases. He was middle-aged and had learned to code a few months ago. He did not seem interested when I told him that the field was called 'bioinformatics' and that there were many people working on these problems already. This is not a "low probability of success", this is a zero chance of success. In these cases, I'm not sure what the right course of action is. I don't think discouragement even does anything; for a particular kind of person (who has the arrogance to think they could cure a major disease as though it were a blue ocean problem), active discouragement just solidifies their resolve. I like to think that if they could redirect their ambition to a small and tractable problem, they might actually be able to make a contribution (even Terry Davis of TempleOS fame was able to produce something inspiring, which he wouldn't have done if he had been trying to Solve a Big Problem). But then I think you're probably right, that there is no real hope, and the best course is to ignore them so I'm not wasting my time, but also to let them have a dream and feel like they're doing something.
  - 8y ago
leecarraher 8y ago
A simple litmus test that saves you from most clickbait, si whether the actual paper title contains, more-or-less, the equation P=NP or P!=NP. I cite Andrew Wile's proof of Fermat's Last Theorem, titled "Modular Forms, Elliptic Curves and Galois Representations" . The title will be about the how, and not some pop article title.
- Ar-Curunir 8y ago
  On as a counterexample, the paper showing that primality checking is in P was called "Primes is in P"
  - dlubarov 8y ago
    Another counterexample is "IP = PSPACE" by Shamir. I think it's nice when titles include the main result plus a few words about methodology, like "IP = PSPACE using Error Correcting Codes", or "The PCP Theorem by Gap Amplification".
- dagw 8y ago
  The title "Modular Forms, Elliptic Curves and Galois Representations" was the title of his talk where he first presented his proof. He chose that title because he wanted to keep the fact the he'd actually proven FLT as a surprise twist for the end of his talk and did want and 'spoilers' The 'Modular Forms, Elliptic Curves..." part of the title comes from the fact that Wiles' approach wasn't to directly prove FLT. What he did was prove something called Taniyama–Shimura–Weil conjecture, which is a statement about the connections between modular forms and elliptic curves. It was already known at the time (thanks to Ribet's Theorem) that Taniyama–Shimura–Weil being true also would mean that FLT had to be true as a consequence of the conjecture.
amingilani 8y ago
>Yes, this post is about our own “claimers” in complexity theory. >The TV Claimers meet a grisly end. We will not say any more about it. We want to be nice. >Please: Do not stop reading. Yes we know that it is likely that no claimer really has such a proof. I understand the author's frustration on the subject, but I don't think his disdain is warranted. This reminds me of the time Mehdi Sadaghdar, who runs the YouTube channel ElectroBOOM, disagreed with former MIT Professor Dr. Walter Lewin's proposal that Kirchhoff's Law is "for the birds". Sadaghdar reproduced the results from Dr. Lewin's experiments, but proposed an alternative explanation about what could be happening. He created a video for Dr. Lewin, and stated that he was open to being proven wrong, ending that "either way, the science will win". Dr. Lewin's response, instead of educational, was belittling where he generalized Sadaghdar as one of the group that holds to Kirchhoff's Law "religiously", and that he needs better education. The explanation was wrapped around in copious amounts of disdain. Sadaghdar eventually realized that they both fundamentally believed the same thing, and that their disagreement was only an error in communication, however, Dr. Lewin's videos are far more disliked than liked, and he didn't come out appearing to be the good guy from the exchange. My point is, maybe generalizing the people you're criticizing, even though you "think the vast majority of claimers of P=NP or other big results have almost always worked alone" and comparing them to a group of people who die a "grisly" death in a fictional TV series, before you begin a lecture, isn't educational. [0]: Sadaghdar's original video: https://www.youtube.com/watch?v=0TTEFF0D8SA https://www.youtube.com/watch?v=0TTEFF0D8SA [1]: Dr. Lewin's response video 1: https://youtu.be/AQqYs6O2MPw https://youtu.be/AQqYs6O2MPw [2]: Dr. Lewin's response video 2: https://youtu.be/ototTU5NUNA https://youtu.be/ototTU5NUNA [3]: Dr. Lewin's response video 3: https://youtu.be/d_XqrZo5_7Y https://youtu.be/d_XqrZo5_7Y [4]: Sadaghdar's last video: https://www.youtube.com/watch?v=Q9LuVBfwvzA https://www.youtube.com/watch?v=Q9LuVBfwvzA
- HAL9000Ti 8y ago
  I was bracing for you to reveal that Sadaghdar was right all along and that Dr.Lewin was wrong but.. in the end it's about whose youtube video like / dislike ratio is better?
  - amingilani 8y ago
nabla9 8y ago
Carl Sagan once complained that all people who contacted him and claimed to talk with aliens always reseived simple unoriginal messages like love each other. Aliens never provided anything humans did not already know. If someone comes up with a proof, they are in good position to troll.
- kristopolous 8y ago
  Can you imagine if it was the other way? "Well I have no idea what it means, but they said these few sheets of math would be interesting to you and I thought you'd like to have them."
  - wolfgke 8y ago
    > Can you imagine if it was the other way? "Well I have no idea what it means, but they said these few sheets of math would be interesting to you and I thought you'd like to have them." I can easily imagine that there exist lots of math nerds with a love for alien conspiracies in the internet who are keen on decoding these formulas.
    - kristopolous 8y ago
      I'd imagine something actually revolutionarily useful would probably have controversial assumption breaking conventions that people would be very skeptical of along with some novel concepts and definitions most wouldn't see any value or sense in. If this were to actually happen, I think most people would discount it as gibberish because it would appear to be wrong things based on inventiveness and misunderstanding. Which if someone with a fields medal published you take seriously but if it's someone who works retail and is talking about aliens, you're probably going to ignore. There's a twilight zone episode about that where someone travels back in time to prevent things but isn't taken seriously and can't stop disasters.
    - jtolmar 8y ago
      You could go around asking successful mathematicians to write out some of their favorite unsubstantiated hunches and post a compilation of them as an alien message.
mlthoughts2018 8y ago
I dislike the early section about arrogance. Who cares? I don’t care if someone is being arrogant, humble, or anything else, when it comes to mathematics proofs. Imagine if Hardy had scolded Ramanujan for being “arrogant” and dismissed his correspondence? At best, by trying to judge arrogance, you’re trying to use it as some type of correlate with being a crank and more quickly dismiss a claim without spending the effort to read it. At worst, it’s trying to entrench the superficial credential of mathematics academia and journal publication style of collaboration and peer review, which frankly (and especially in mathematics, where polymath amateurs can easily be responsible for ground-breaking solo work) is overdue for being replaced by a more fully open, unrestricted participation model of discovery and publication. Some arrogant cranks are going propose time-waster claims. Just accept it. Don’t care if they are arrogant or not.
viraghrr 8y ago
I'm a crank. I found this article very valuable. In 2010 I put online a brief refutation of the EMH, the efficient market hypothesis. Here it is: https://arxiv.org/abs/1011.0423 https://arxiv.org/abs/1011.0423 If I had seen this then, I think I would have followed the directions in the inset box, where the article suggests saying something like: "The reason I succeeded in finding an algorithm for P=NP is that I noticed that... No one else seems to see that this insight is very powerful. It is very useful since it implies ..." I could have simply written: "Nobody has bothered to test the Efficient Market Hypothesis, but since I have some background in computer science I made an unusual mental connection, and it follows that it doesn't need to be tested. It cannot be true." (My proof outlined a way to show it has to be false.) I remember my thinking at the time was that I didn't need to explain it at all, just make it correct and brief. At the time, I didn't want to include anything personal in the paper. Perhaps I should have. It's not a very good paper.
- roywiggins 8y ago
  Isn't this equivalent to saying "I have incorporated a company, it owns a lockbox, and only I know what's inside." Only an insider knows the real value. But even Wikipedia's summation of the strongest version of EMH says that it's impossible if insider information can be hidden: "If there are legal barriers to private information becoming public, as with insider trading laws, strong-form efficiency is impossible" https://en.wikipedia.org/wiki/Efficient-market_hypothesis#Strong-form_efficiency https://en.wikipedia.org/wiki/Efficient-market_hypothesis#St... So it seems that your contention- that insider information that hasn't leaked yet obviously won't be reflected in the price- is spelled out already.
  - viraghrr 8y ago
    okay so going with your analogy it's like publishing a picture of what's inside the vault but you publish the picture encrypted. imagine the encryption is a 20-letter random password in winzip (imagine winzip is secure) with the picture of what is in the vault. Although only an insider knows what's in the vault, the public gets the encrypted picture. Every day you publish one more letter of the passwrod. So if the password is p?jbAL;nQpg-37(z(feH then on day 1 you publish just "p" (the first letter) so now it's as strong as 19-letter password since you gave them the first letter. I don't know what will happen exactly between day 1 and day 20, but on day 19 anyone can just try every 20-leter password with the first 19 letters you've published by that date. So if by then you've published p?jbAL;nQpg-37(z(fe already they'll just try p?jbAL;nQpg-37(z(feA p?jbAL;nQpg-37(z(feB p?jbAL;nQpg-37(z(feC p?jbAL;nQpg-37(z(feD in winzip. Anyone can just try all of them until they find the one that unlocks it. So on day 19 if it's worth knowing, for sure someone will take a minute or two to try it. Not that hard if there's just 1 missing letter. So for sure if you tell people it's a 20-letter password and give them 19 letters they will figure it out before you've given them the last letter. All right, but on day 1 nobody can guess all 20 characters in the password. That's too hard. it's impossible. So every day you make it easier, but it'll be "broken" sometime between day 1 and day 20, assuming that the insider information doesn't leak in any other way. that means that someone will break it but not on day 1. on some day between day 1 and day 20. The person who analyzes it "best" will have the insider information first, but for sure we don't have to wait until day 20 because by then it's ridiculously easy to analyze. meanwhile you're making the analysis easier and easier. the person who can do the analysis best will have it first, and this proves that there's no "infinitely great analysis" already being done all the time by public markets. it's a simple demonstration of this fact. I don't think you actually need to do the experiment to now the results. hope this helps.
dunkelheit 8y ago
Thoroughly boring and conventional advice. How about some advice from the dark side: First, become a distinguished researcher in the field so that there is no other choice but to take you seriously. Then write a giant multi-part book-length paper consisting almost entirely of endless definitions and lemmas referring to each other. To those brave souls who actually try to read and understand the paper and who claim that they have found a problem with it, reply that they have profoundly misunderstood the nature of the work and should read the paper more carefully. Not actual advice of course. I just find the controversy surrounding Mochizuki's purported proof of the abc conjecture (HN discussion: https://news.ycombinator.com/item?id=18034714 https://news.ycombinator.com/item?id=18034714) fascinating. Something like this could easily happen to P=NP when one cannot confidently state whether we have a proof or not.
erichocean 8y ago
If you have a proof that P=NP, the best way to demonstrate that is to solve a nice, hard 3-SAT problem. Maybe reversing something like siphash, or something similarly difficult. Set up a web page where someone can put in their 128-bit SIP hash and their plaintext, and you'll tell them the 64-bit secret used to hash it. Everyone will believe you. For extra bonus $$$, there are various large prizes (e.g. $1M USD) you can win if you can "break" various things which are trivially breakable if P=NP. Might as well cash in there, too before they pull the plug on the contest…
- lisper 8y ago
  That's a good idea, but it won't work for a non-constructive proof.
  - kelnage 8y ago
    Nor would it necessarily work (quickly) if the order of magnitude for any constants were sufficiently large (after all, a runtime of 2 * N and a runtime of (2^512) * N are both O(N)). If I remember correctly, in the semi-regular survey conducted with CS experts about this question, the most likely explanation that accompanied a response saying they believed that it may be the case that P=NP was “...but with very large constants”.
  - erichocean 8y ago
    I personally distrust all non-constructive proofs as a matter of principle, and can't think of a single one I would actually miss in practice, let alone one I find convincing. They all smack of begging the question to me. I especially distrust non-constructive proofs that involve first constructing objects in an impossible manner (like, say, sorting an infinite set of infinitely long bit strings—I'm looking at you, Cantor)—and then (ab-)using the reader's intuition about actual things you can construct to "prove" nonsense about things you clearly can't. Which is a long way of saying that I'll only accept a constructive proof that P != NP (or vice versa).
    - deleted 8y ago
      [deleted]
lisper 8y ago
Here are two good practice problems for testing your personal bogometer: http://sparsey.com http://sparsey.com https://www.agilepq.com https://www.agilepq.com It's not P=NP but two similar problems that attract a lot of quackery.
- pmiller2 8y ago
  Are those even serious sites? They look like what happens when a Markov chain program meets a mediocre web designer.
  - lisper 8y ago
    Sadly, yes. I personally know someone who has invested in one of them :-(
  - CodiePetersen 8y ago
    I can assure you that Rod Rinkus', Sparsey creator, work is very serious. He is a computational neuro scientist I've actually been working with him since october. But he has said the website has needed some updating for a while now. One of my primary jobs will be to get the demos up and running with a more updated feel. I'm not sure of the other site, but I have done the work to recreate Rod's work from scratch and he has done several tests to prove the system works. Most of his work was done through DARPA and ONR research grants. He has only really recently decided to try to make a profitable company off of it recently, before that it has always been funded through research grants. As for the look and feel of the website, which in reality has no merit on whether the research is legitimate or not, I have joked that he just needs to market himself better and he has laughingly agreed. But you can hit him or I up if the research is to hard to understand from a glance. We are trying to practice how to pitch it to people better so it's easier to understand. But once every thing clicks, its actually a really simple concept, it's just that its a highly recurrent system. I had to program it out piece by piece before things started making sense.
- CodiePetersen 8y ago
  I'd like to know what you don't understand about the Sparsey algorithm that makes you think it is "quackery". I've programmed it from scratch (I've been working with him since October), Rod Rinkus has several tests that have proven it, Paul Franzon designed GPU & SIMD architectures and an ASIC chip and tested it against Numenta's HTM's which Rod's was faster but consumed more power, and also DARPA & ONR have granted him research grants to develop the algorithm. So I think your claims of quackery are a bit unfounded, but I'd still like to know your thoughts. If there are people out there who think it is impossible or lacks credibility then we need to address that. I hope it's not just the website look xD. He has been saying he needs to change the website because it's old but he hasn't done so yet.
Lucent 8y ago
This article should really be deleted. It's giving crackpots advice for camouflaging their crackpottery, forcing serious mathematicians to waste more of their time determining its legitimacy.
- nullc 8y ago
  Actually, if a crackpot can faithfully camouflage their output then they are probably not crackpotty enough to deserve deletion without any consideration at all. Imagine, you have succesfully proved P eq/neq NP... but you can't be bothered to learn LaTeX or convince someone who does to typeset your work? Unfreeking likely. The vast bulk of the junk can be disregarded by simple heuristics because the crackpots are unwilling or unable to meet even a very low bar. Telling them precisely where the bar is will only get a small amount past it.
js8 8y ago
I recently became interested about P=NP, the reason was learning. And I became crankish, in the sense of trying to understand the problem myself. My advice is - learn about naturalness. Monotone circuit bound in CLIQUE in particular is an interesting result, which knocks out many straightforward approaches to show that P=NP. The Wigderson recent book gives a very good overview. However, I wish in some sense this was better explained, that there was more examples of algorithms that cannot work because they can be, in some sense, represented as monotone circuits.
raincom 8y ago
Here is a guy, who did not know LaTeX, but written in MS word: https://www.quantamagazine.org/statistician-proves-gaussian-correlation-inequality-20170328/ https://www.quantamagazine.org/statistician-proves-gaussian-...

153 points by furcyd 8y ago

By the name, I was expecting this article to be much more technical, giving examples of common errors made by attempted proofs or reasons why certain cruxes in possible proofs would be difficult to overcome.

kkylin 8y ago
So was I, something more like this: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.3404&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.... Still, I thought it was a nice post.

w8rbt 8y ago

Very smart people have tried for a very long time to show one way or the other. We don't know if P = NP (seems unlikely) or if P != NP (seems likely). But there is no proof either way. If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Again, this seems very unlikely.

tyilo 8y ago
You assume that the proof for P = NP would be constructive.
- pascal_cuoq 8y ago
  It's automatically constructive. Algorithms can be enumerated. Proofs can be enumerated. For any formalized problem Q in NP, you can always simply enumerate algorithms A and candidate proofs P until you stumble on a pair (A, P) where P is a proof that A answers Q in polynomial time. If P=NP, this first step takes constant time (long but independent on the input). If P!=NP, this first step takes forever. In other words, if you have a non-constructive proof that P=NP, just make “search for the polynomial algorithm” the first step of the algorithm, and now you have a constructive proof.
  - saagarjha 8y ago
    > Algorithms can be enumerated. Proofs can be enumerated. How exactly do you do this?
    - jcranmer 8y ago
      Checking whether a string is a valid proof can be done in polynomial time. So, enumerate all possible strings, and check if each string is a valid proof of what you're trying to find.
      - saagarjha 8y ago
        But enumerating all the possible strings takes infinite time? Or, wait, is this saying that since there is some algorithm you can spend some constant amount of time to find it that doesn’t affect the time complexity of your algorithm? I’m not sure I’d call that “constructive”.
        jcranmer 8y ago
        If you know that such a proof exists, then it's guaranteed to terminate.
        kd0amg 8y ago
        is this saying that since there is some algorithm you can spend some constant amount of time to find it Yes. I’m not sure I’d call that “constructive”. The method for constructing the algorithm is given!
      - andrewla 8y ago
        > Checking whether a string is a valid proof can be done in polynomial time. That's not true. Curry-Howard says that determining if a proof is correct has the same complexity as programs in general. Even if P=NP, there are still complexity classes strictly larger than P; say EXP, that would result in a proof requiring exponential time to check for validity. That's assuming that "validity" here means true/false-ness, rather than syntactical validity, which is much less useful.
andrewla 8y ago
> If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Knuth himself, for example, has casually expressed the opinion (not a proof) that P=NP in the past. When you say "as easily" it belies the nature of polynomial time questions. If it turns out that we can produce an algorithm for 3SAT that is O(n^1e72), then that will in fact prove that P=NP. But this does not make any practical problems "easy".
- CJefferson 8y ago
  No need for n^1e72, a SAT instance with a couple of hundred variables can usually be solved easily, industrial instances are often hundreds of thousands of variables. Even a O(n^10) algorithm would be of MASSIVE theoretical interest, but almost no practical value.
- mcguire 8y ago
  https://www.scottaaronson.com/blog/?p=122 https://www.scottaaronson.com/blog/?p=122 See #5. And... https://www.scottaaronson.com/blog/?p=3095 https://www.scottaaronson.com/blog/?p=3095
jcranmer 8y ago
I suspect most people, even most computer scientists, have a very limited view of complexity theory. When Big-O notation is introduced, and we discuss algorithms, we tend to only ever come across them in contexts where the algorithm is "small" polynomial or "small" hidden constants are present. How many people can even name a polynomial algorithm that's worse than cubic, or a polynomial algorithm with a massive hidden constant? In practice, these algorithms tend to be hidden in nasty combinatorial problems which sometimes are themselves contrived mainly to force a solution that slow. Yet the evidence suggests that, should P=NP, then the polynomial algorithm is going to be of that nasty combinatorial variety. The main reason for this, informally of course, is that NP-complete problems tend to have their NP-completeness arise from specifically hard instances, rather than generally being hard. SAT is NP-complete, but we can solve many SAT queries we care about (undoing cryptographic algorithms are of course the exception--by design). Graph coloring is NP-complete, except if your graph falls into one of several dozen special cases of graphs which covers most we know about. In other words, there's a kernel of instances where there structure is exponentially complex and there's no way to develop heuristics that are meaningfully simpler than "try every possibility until one works." It is possible that there exists some basis that can describe the complex structure in polynomial terms, but this basis would itself have to embed the complexity we see, and as such, it would be one of those combinatorial monstrosities. Think something of the terms of 3^2^16 as your hidden constant (that's the bounds for the "simple" algorithm in the L=SL paper).
- ahelwer 8y ago
  Something I've always wondered - if only certain instances of 3SAT are difficult, why are those considered the same problem as easy instances of 3SAT? Why do we say 3SAT is hard, rather than 3SAT with specific structure? Or do we lack the ability to determine whether a given instance of 3SAT is hard?
  - jcranmer 8y ago
    We use the worst-case analysis to drive Big-O notation; if the worst case is hard, then we say the problem itself is hard. This is the main limitation of Big-O, as normally taught: it tends to ignore the practicability of the algorithm for typical cases. Usually, the practice for solving these sorts of problems is to have your algorithm return three values: the solution, unsatisfiable, or timed out. There is literature on how to structure such problems to make it more likely you're going to get answers, but I'm not personally familiar with this area.

throwawaymath 8y ago

On a related note, Scott Aaronson once wrote up a few heuristics he uses to quickly evaluate how likely a P/NP proof is to be incorrect: https://www.scottaaronson.com/blog/?p=458 https://www.scottaaronson.com/blog/?p=458 Aaronson’s rules are more technical than the ones given in this article, the latter of which can be generally applied to most claimed (dis)proofs of famous open problems. In particular, poorly typeset papers from a solo, unknown authors are highly unlikely to be correct when they’re claiming to resolve well known open problems. In regard to the P/NP problem specifically, Aaronson’s examples of weaker open problems which would likely be resolved first - or at least accounted for in some nontrivial way - are analogous to this article’s point about proving weaker theorems first. It would be very suspicious for a proof that P and NP are separable (or not separable) to work at such a high level that it doesn’t prove also new results about the lower bounds of a litany of other problems.

mormegil 8y ago
I thought you meant a simpler heuristic http://haspvsnpbeensolved.com/ http://haspvsnpbeensolved.com/ :-)(I had thought Scott Aaronson is somehow connected with it, but probably not, it seems)
- btrettel 8y ago
  I know the guy who made that website. I think it might have been done at the request of Scott, or Scott advertised it on his blog at some point.
- pmiller2 8y ago
  That’s kinda funny, but it should at least throw an error when you click the button without providing a URL. :P
- verma7 8y ago
  I hope to see the day when this website gives the wrong answer.
neilv 8y ago
Is all the good math institutionalized now (e.g., you can't do good math without all the benefit of learning background within the institution conventions)? What's the intuition that an extremely important proof will come from someone who gets all the TeX tweaked to camera-ready perfection, goes around and gives the talks, and all the conventional things... rather than a genius out of nowhere who walks into a stranger's office, wordlessly drops on their desk a stack of handwritten pages wrapped in twine, and walks out, never to be seen again? I was thinking of this because I once knew an autistic person, from some humble and isolated upbringing, who was getting some informal math instruction, and they told me they thought they knew a proof for P=NP. I considered it extremely unlikely, but not utterly impossible. (They reportedly tested "off the scale" high in some particular cognitive regard, and I'd noticed a couple minor superpowers.) If that person, to use them as an example, ever actually worked out the proof, and wanted to "turn it in" with their own judgment and access, I wonder where they'd go. And whether it would be somewhere that would take them seriously enough to look at it, and whether they could tell that a proof in unconventional terms had merit. If they get turned away from the first place, would they be discouraged and give up, or would they keep trying, there or elsewhere. If they persisted, would they appear to be a crank because of their persistence and frustration.

ryanstrug 8y ago

P=NP because all inputs and outputs can be represented by a 1’s/0’s number and a line can be drawn between those numbers that’s O(1) and all sets of algorithms are arbitrary so it’s possible to have a set of algorithms that fits the P=NP definition, k thx bye.

ryanstrug 8y ago
‪More specifically algorithms solve arbitrary sets of inputs and outputs. Different algorithms can be aligned with different sets of inputs and outputs that are less natural but within the P=NP criteria.‬
Chirono 8y ago
I suspect you're just trolling, but for anyone else: This is true for any bounded input, yes, but doesn't hold for an infinite domain.

deleted 8y ago

[deleted]

AnaniasAnanas 8y ago

Just wondering, why do people not use Coq/Isabelle/Agda/etc in order to check such proofs? Wouldn't that save them from the "shame" of producing yet-another-incorrect P(!)=NP proof?

throwawaymath 8y ago
They don't do it because the technology just isn't there yet. Automated theorem checking is typically very difficult for any nontrivial theorem; automated theorem generation is so extraordinarily difficult, it's generally infeasible. The steps to construct a proof of a theorem are as follows: 1. Formally define a language specification which will ostensibly contain the theorem statement and a proof. 2. Search the language space (the set of all strings of the language) for a proof of the theorem statement. 3. If step 2 fails, change the language specification to include prerequisite mathematics or an alternative statement of the theorem. Even when you exploit clever structural properties of the theorem statement and the language definition, it's extremely easy to encounter a combinatorial explosion when you search for a proof. On the other hand, suppose you already have a proof and simply want to verify it using a proof assistant. In order to do so, the language you define must be able to automatically verify all prerequisite mathematics which your proof depends on. Encoding that mathematics into a language is difficult and tedious, and dependency checking is itself vulnerable to combinatorial explosion. It's a very active area of research in its own right, but it can't obviate this problem for the foreseeable future.
- andrewla 8y ago
  > Automated theorem checking is typically very difficult for any nontrivial theorem I'm not sure this is true -- I thought the whole idea of these theorem systems was to make the kernel of the proof system as simple as possible (to allow a manual proof, or at least high confidence of correctness). If your program can produce an instance of a type, and it type-checks, then it true. Type inference can be tricky, and a lot of what makes the systems usable is the fact that you can omit types and allow the compiler to infer them, but a fully-expressed typed proof outline is enough to quickly verify correctness of the proof.

amiune 8y ago

Why to discourage people to try things with low probability of success? It's hard to find these guys, let them be happy at least for a while

jerf 8y ago
You're welcome to try all you want. But after the hundredth crackpot paper someone receives, expect them to be a wee bit less welcoming, open, and excited than they were the first couple of times. I think a lot of people commenting on this topic to this effect are obviously not receiving a huge deluge of crackpot papers. I've never received them myself, but I've seen a couple of instances of people and companies who do, each of them themselves small instances of the problem, and it would have been plenty to try my patience if I had to spend any time at all on each of them.
rabidrat 8y ago
I received an email from someone I met recently: > I inted to start doing a project on what causes Parkinson's Desease using Python , Big Data, , Data analyt and Nvidia Supercomputing. You have a skillset that can hel sovle this problem and I coul use your help. If we are successful then we can do the same for other medical deseases. He was middle-aged and had learned to code a few months ago. He did not seem interested when I told him that the field was called 'bioinformatics' and that there were many people working on these problems already. This is not a "low probability of success", this is a zero chance of success. In these cases, I'm not sure what the right course of action is. I don't think discouragement even does anything; for a particular kind of person (who has the arrogance to think they could cure a major disease as though it were a blue ocean problem), active discouragement just solidifies their resolve. I like to think that if they could redirect their ambition to a small and tractable problem, they might actually be able to make a contribution (even Terry Davis of TempleOS fame was able to produce something inspiring, which he wouldn't have done if he had been trying to Solve a Big Problem). But then I think you're probably right, that there is no real hope, and the best course is to ignore them so I'm not wasting my time, but also to let them have a dream and feel like they're doing something.
- 8y ago

leecarraher 8y ago

A simple litmus test that saves you from most clickbait, si whether the actual paper title contains, more-or-less, the equation P=NP or P!=NP. I cite Andrew Wile's proof of Fermat's Last Theorem, titled "Modular Forms, Elliptic Curves and Galois Representations" . The title will be about the how, and not some pop article title.

Ar-Curunir 8y ago
On as a counterexample, the paper showing that primality checking is in P was called "Primes is in P"
- dlubarov 8y ago
  Another counterexample is "IP = PSPACE" by Shamir. I think it's nice when titles include the main result plus a few words about methodology, like "IP = PSPACE using Error Correcting Codes", or "The PCP Theorem by Gap Amplification".
dagw 8y ago
The title "Modular Forms, Elliptic Curves and Galois Representations" was the title of his talk where he first presented his proof. He chose that title because he wanted to keep the fact the he'd actually proven FLT as a surprise twist for the end of his talk and did want and 'spoilers' The 'Modular Forms, Elliptic Curves..." part of the title comes from the fact that Wiles' approach wasn't to directly prove FLT. What he did was prove something called Taniyama–Shimura–Weil conjecture, which is a statement about the connections between modular forms and elliptic curves. It was already known at the time (thanks to Ribet's Theorem) that Taniyama–Shimura–Weil being true also would mean that FLT had to be true as a consequence of the conjecture.

amingilani 8y ago

>Yes, this post is about our own “claimers” in complexity theory. >The TV Claimers meet a grisly end. We will not say any more about it. We want to be nice. >Please: Do not stop reading. Yes we know that it is likely that no claimer really has such a proof. I understand the author's frustration on the subject, but I don't think his disdain is warranted. This reminds me of the time Mehdi Sadaghdar, who runs the YouTube channel ElectroBOOM, disagreed with former MIT Professor Dr. Walter Lewin's proposal that Kirchhoff's Law is "for the birds". Sadaghdar reproduced the results from Dr. Lewin's experiments, but proposed an alternative explanation about what could be happening. He created a video for Dr. Lewin, and stated that he was open to being proven wrong, ending that "either way, the science will win". Dr. Lewin's response, instead of educational, was belittling where he generalized Sadaghdar as one of the group that holds to Kirchhoff's Law "religiously", and that he needs better education. The explanation was wrapped around in copious amounts of disdain. Sadaghdar eventually realized that they both fundamentally believed the same thing, and that their disagreement was only an error in communication, however, Dr. Lewin's videos are far more disliked than liked, and he didn't come out appearing to be the good guy from the exchange. My point is, maybe generalizing the people you're criticizing, even though you "think the vast majority of claimers of P=NP or other big results have almost always worked alone" and comparing them to a group of people who die a "grisly" death in a fictional TV series, before you begin a lecture, isn't educational. [0]: Sadaghdar's original video: https://www.youtube.com/watch?v=0TTEFF0D8SA https://www.youtube.com/watch?v=0TTEFF0D8SA [1]: Dr. Lewin's response video 1: https://youtu.be/AQqYs6O2MPw https://youtu.be/AQqYs6O2MPw [2]: Dr. Lewin's response video 2: https://youtu.be/ototTU5NUNA https://youtu.be/ototTU5NUNA [3]: Dr. Lewin's response video 3: https://youtu.be/d_XqrZo5_7Y https://youtu.be/d_XqrZo5_7Y [4]: Sadaghdar's last video: https://www.youtube.com/watch?v=Q9LuVBfwvzA https://www.youtube.com/watch?v=Q9LuVBfwvzA

HAL9000Ti 8y ago
I was bracing for you to reveal that Sadaghdar was right all along and that Dr.Lewin was wrong but.. in the end it's about whose youtube video like / dislike ratio is better?
- amingilani 8y ago

nabla9 8y ago

Carl Sagan once complained that all people who contacted him and claimed to talk with aliens always reseived simple unoriginal messages like love each other. Aliens never provided anything humans did not already know. If someone comes up with a proof, they are in good position to troll.

kristopolous 8y ago
Can you imagine if it was the other way? "Well I have no idea what it means, but they said these few sheets of math would be interesting to you and I thought you'd like to have them."
- wolfgke 8y ago
  > Can you imagine if it was the other way? "Well I have no idea what it means, but they said these few sheets of math would be interesting to you and I thought you'd like to have them." I can easily imagine that there exist lots of math nerds with a love for alien conspiracies in the internet who are keen on decoding these formulas.
  - kristopolous 8y ago
    I'd imagine something actually revolutionarily useful would probably have controversial assumption breaking conventions that people would be very skeptical of along with some novel concepts and definitions most wouldn't see any value or sense in. If this were to actually happen, I think most people would discount it as gibberish because it would appear to be wrong things based on inventiveness and misunderstanding. Which if someone with a fields medal published you take seriously but if it's someone who works retail and is talking about aliens, you're probably going to ignore. There's a twilight zone episode about that where someone travels back in time to prevent things but isn't taken seriously and can't stop disasters.
  - jtolmar 8y ago
    You could go around asking successful mathematicians to write out some of their favorite unsubstantiated hunches and post a compilation of them as an alien message.

mlthoughts2018 8y ago

I dislike the early section about arrogance. Who cares? I don’t care if someone is being arrogant, humble, or anything else, when it comes to mathematics proofs. Imagine if Hardy had scolded Ramanujan for being “arrogant” and dismissed his correspondence? At best, by trying to judge arrogance, you’re trying to use it as some type of correlate with being a crank and more quickly dismiss a claim without spending the effort to read it. At worst, it’s trying to entrench the superficial credential of mathematics academia and journal publication style of collaboration and peer review, which frankly (and especially in mathematics, where polymath amateurs can easily be responsible for ground-breaking solo work) is overdue for being replaced by a more fully open, unrestricted participation model of discovery and publication. Some arrogant cranks are going propose time-waster claims. Just accept it. Don’t care if they are arrogant or not.

viraghrr 8y ago

I'm a crank. I found this article very valuable. In 2010 I put online a brief refutation of the EMH, the efficient market hypothesis. Here it is: https://arxiv.org/abs/1011.0423 https://arxiv.org/abs/1011.0423 If I had seen this then, I think I would have followed the directions in the inset box, where the article suggests saying something like: "The reason I succeeded in finding an algorithm for P=NP is that I noticed that... No one else seems to see that this insight is very powerful. It is very useful since it implies ..." I could have simply written: "Nobody has bothered to test the Efficient Market Hypothesis, but since I have some background in computer science I made an unusual mental connection, and it follows that it doesn't need to be tested. It cannot be true." (My proof outlined a way to show it has to be false.) I remember my thinking at the time was that I didn't need to explain it at all, just make it correct and brief. At the time, I didn't want to include anything personal in the paper. Perhaps I should have. It's not a very good paper.

roywiggins 8y ago
Isn't this equivalent to saying "I have incorporated a company, it owns a lockbox, and only I know what's inside." Only an insider knows the real value. But even Wikipedia's summation of the strongest version of EMH says that it's impossible if insider information can be hidden: "If there are legal barriers to private information becoming public, as with insider trading laws, strong-form efficiency is impossible" https://en.wikipedia.org/wiki/Efficient-market_hypothesis#Strong-form_efficiency https://en.wikipedia.org/wiki/Efficient-market_hypothesis#St... So it seems that your contention- that insider information that hasn't leaked yet obviously won't be reflected in the price- is spelled out already.
- viraghrr 8y ago
  okay so going with your analogy it's like publishing a picture of what's inside the vault but you publish the picture encrypted. imagine the encryption is a 20-letter random password in winzip (imagine winzip is secure) with the picture of what is in the vault. Although only an insider knows what's in the vault, the public gets the encrypted picture. Every day you publish one more letter of the passwrod. So if the password is p?jbAL;nQpg-37(z(feH then on day 1 you publish just "p" (the first letter) so now it's as strong as 19-letter password since you gave them the first letter. I don't know what will happen exactly between day 1 and day 20, but on day 19 anyone can just try every 20-leter password with the first 19 letters you've published by that date. So if by then you've published p?jbAL;nQpg-37(z(fe already they'll just try p?jbAL;nQpg-37(z(feA p?jbAL;nQpg-37(z(feB p?jbAL;nQpg-37(z(feC p?jbAL;nQpg-37(z(feD in winzip. Anyone can just try all of them until they find the one that unlocks it. So on day 19 if it's worth knowing, for sure someone will take a minute or two to try it. Not that hard if there's just 1 missing letter. So for sure if you tell people it's a 20-letter password and give them 19 letters they will figure it out before you've given them the last letter. All right, but on day 1 nobody can guess all 20 characters in the password. That's too hard. it's impossible. So every day you make it easier, but it'll be "broken" sometime between day 1 and day 20, assuming that the insider information doesn't leak in any other way. that means that someone will break it but not on day 1. on some day between day 1 and day 20. The person who analyzes it "best" will have the insider information first, but for sure we don't have to wait until day 20 because by then it's ridiculously easy to analyze. meanwhile you're making the analysis easier and easier. the person who can do the analysis best will have it first, and this proves that there's no "infinitely great analysis" already being done all the time by public markets. it's a simple demonstration of this fact. I don't think you actually need to do the experiment to now the results. hope this helps.

dunkelheit 8y ago

Thoroughly boring and conventional advice. How about some advice from the dark side: First, become a distinguished researcher in the field so that there is no other choice but to take you seriously. Then write a giant multi-part book-length paper consisting almost entirely of endless definitions and lemmas referring to each other. To those brave souls who actually try to read and understand the paper and who claim that they have found a problem with it, reply that they have profoundly misunderstood the nature of the work and should read the paper more carefully. Not actual advice of course. I just find the controversy surrounding Mochizuki's purported proof of the abc conjecture (HN discussion: https://news.ycombinator.com/item?id=18034714 https://news.ycombinator.com/item?id=18034714) fascinating. Something like this could easily happen to P=NP when one cannot confidently state whether we have a proof or not.

erichocean 8y ago

If you have a proof that P=NP, the best way to demonstrate that is to solve a nice, hard 3-SAT problem. Maybe reversing something like siphash, or something similarly difficult. Set up a web page where someone can put in their 128-bit SIP hash and their plaintext, and you'll tell them the 64-bit secret used to hash it. Everyone will believe you. For extra bonus $$$, there are various large prizes (e.g. $1M USD) you can win if you can "break" various things which are trivially breakable if P=NP. Might as well cash in there, too before they pull the plug on the contest…

lisper 8y ago
That's a good idea, but it won't work for a non-constructive proof.
- kelnage 8y ago
  Nor would it necessarily work (quickly) if the order of magnitude for any constants were sufficiently large (after all, a runtime of 2 * N and a runtime of (2^512) * N are both O(N)). If I remember correctly, in the semi-regular survey conducted with CS experts about this question, the most likely explanation that accompanied a response saying they believed that it may be the case that P=NP was “...but with very large constants”.
- erichocean 8y ago
  I personally distrust all non-constructive proofs as a matter of principle, and can't think of a single one I would actually miss in practice, let alone one I find convincing. They all smack of begging the question to me. I especially distrust non-constructive proofs that involve first constructing objects in an impossible manner (like, say, sorting an infinite set of infinitely long bit strings—I'm looking at you, Cantor)—and then (ab-)using the reader's intuition about actual things you can construct to "prove" nonsense about things you clearly can't. Which is a long way of saying that I'll only accept a constructive proof that P != NP (or vice versa).
  - deleted 8y ago
    [deleted]

lisper 8y ago

Here are two good practice problems for testing your personal bogometer: http://sparsey.com http://sparsey.com https://www.agilepq.com https://www.agilepq.com It's not P=NP but two similar problems that attract a lot of quackery.

pmiller2 8y ago
Are those even serious sites? They look like what happens when a Markov chain program meets a mediocre web designer.
- lisper 8y ago
  Sadly, yes. I personally know someone who has invested in one of them :-(
- CodiePetersen 8y ago
  I can assure you that Rod Rinkus', Sparsey creator, work is very serious. He is a computational neuro scientist I've actually been working with him since october. But he has said the website has needed some updating for a while now. One of my primary jobs will be to get the demos up and running with a more updated feel. I'm not sure of the other site, but I have done the work to recreate Rod's work from scratch and he has done several tests to prove the system works. Most of his work was done through DARPA and ONR research grants. He has only really recently decided to try to make a profitable company off of it recently, before that it has always been funded through research grants. As for the look and feel of the website, which in reality has no merit on whether the research is legitimate or not, I have joked that he just needs to market himself better and he has laughingly agreed. But you can hit him or I up if the research is to hard to understand from a glance. We are trying to practice how to pitch it to people better so it's easier to understand. But once every thing clicks, its actually a really simple concept, it's just that its a highly recurrent system. I had to program it out piece by piece before things started making sense.
CodiePetersen 8y ago
I'd like to know what you don't understand about the Sparsey algorithm that makes you think it is "quackery". I've programmed it from scratch (I've been working with him since October), Rod Rinkus has several tests that have proven it, Paul Franzon designed GPU & SIMD architectures and an ASIC chip and tested it against Numenta's HTM's which Rod's was faster but consumed more power, and also DARPA & ONR have granted him research grants to develop the algorithm. So I think your claims of quackery are a bit unfounded, but I'd still like to know your thoughts. If there are people out there who think it is impossible or lacks credibility then we need to address that. I hope it's not just the website look xD. He has been saying he needs to change the website because it's old but he hasn't done so yet.

Lucent 8y ago

This article should really be deleted. It's giving crackpots advice for camouflaging their crackpottery, forcing serious mathematicians to waste more of their time determining its legitimacy.

nullc 8y ago
Actually, if a crackpot can faithfully camouflage their output then they are probably not crackpotty enough to deserve deletion without any consideration at all. Imagine, you have succesfully proved P eq/neq NP... but you can't be bothered to learn LaTeX or convince someone who does to typeset your work? Unfreeking likely. The vast bulk of the junk can be disregarded by simple heuristics because the crackpots are unwilling or unable to meet even a very low bar. Telling them precisely where the bar is will only get a small amount past it.

js8 8y ago

I recently became interested about P=NP, the reason was learning. And I became crankish, in the sense of trying to understand the problem myself. My advice is - learn about naturalness. Monotone circuit bound in CLIQUE in particular is an interesting result, which knocks out many straightforward approaches to show that P=NP. The Wigderson recent book gives a very good overview. However, I wish in some sense this was better explained, that there was more examples of algorithms that cannot work because they can be, in some sense, represented as monotone circuits.

raincom 8y ago

Here is a guy, who did not know LaTeX, but written in MS word: https://www.quantamagazine.org/statistician-proves-gaussian-correlation-inequality-20170328/ https://www.quantamagazine.org/statistician-proves-gaussian-...