7 ms·

It's cool that this paper exists as a counterpoint to the pervasive culture of defeat around P == NP. People want to believe P != NP so they feel better about

by 1arity 11y ago

It's cool that this paper exists as a counterpoint to the pervasive culture of defeat around P == NP. People want to believe P != NP so they feel better about how they failed to prove it, or make a faster algorithm. This is ridiculous and doesn't help advance the cause to solve it. It's an illogicality at the heart of the CS establishment, everyone is "confident" P != NP, with no proof, simply so they can move on to other things. What happened to backbone, determination and persistence? Their confidence in impossibility smells of self-justification of failure, and fear. And the irrational "culture of belief" ( without proof ) is the very antithesis of good science. Your downvote makes you complicit to this culture of defeat.

deleted 11y ago
[deleted]
chpatrick 11y ago
Well, it would also be very strange if P=NP because you could use algorithms like this in polynomial time: bool isComposite(n) { guess a number d magically if (n % d == 0) { return true; } else { fail; } }
- mikeash 11y ago
  P = NP just means that there exist some polynomial-time algorithm that's able to solve that problem. It doesn't mean that you can take that pseudocode and run it directly in polynomial time.
  - teraflop 11y ago
    Actually, it kind of does. If P==NP, then any problem in NP is solvable in polynomial time -- including efficient simulation of a non-deterministic Turing machine that supports "guessing correctly" as a primitive operation. That's why the P=?NP problem has such far-reaching implications, and one reason why P==NP is generally believed to be false.
    - 1arity 11y ago
      What's the reduction from 3-SAT to "guessing correctly"?
      - teraflop 11y ago
        The original reduction was given by the well-known Cook-Levin theorem. It's really the existence of this theorem that motivated the entire study of NP-complete problems in the first place. Basically, you can unroll the execution of a non-deterministic Turing machine along the time axis, using separate variables to represent the state of the machine at each time step. All of the rules that govern the Turing machine's execution can be encoded as Boolean formulas, resulting in one giant formula such that the formula is satisfiable iff there is an assignment of variables corresponding to a valid execution. Adding non-determinism (the "guessing") is easy; you just leave particular variables unconstrained. If the original machine runs in polynomial time, then the number of variables and clauses is also polynomial. And of course there's a straightforward polynomial reduction from SAT to 3-SAT. No offense, but if you don't already know about this, it's kind of ironic that you're the one claiming CS researchers are "arrogant" for their beliefs about P=?NP.
    - mikeash 11y ago
      Is efficient simulation of a nondeterministic Turing machine in NP? I don't see how that could be the case. These are decision problems, where you pose a yes/no question, and you get an answer. If a decision problem is in P, then you get your yes/no answer in polynomial time when run on a normal Turing machine. If it's in NP, then you get your yes/no answer in polynomial time when run on a nondeterministic Turing machine. What would be the yes/no answer for "simulation of a non-deterministic Turing machine"? If it's just "the yes/no answer provided by whatever that Turing machine runs" then that problem is clearly not in NP, since you could easily have some code that takes more than polynomial time. Can you restrict it to "the yes/no answer provided by whatever that Turing machine runs, provided that it runs in polynomial time"?
      - teraflop 11y ago
        Well, that comes back to the definition of NP. A problem is in NP iff it is solvable by a non-deterministic Turing machine that is guaranteed to run in polynomial time. If such a machine exists, and P==NP, then the problem is also solvable by a deterministic Turing machine in polynomial time. Strictly speaking, the proof assumes a particular Turing machine. But since universal Turing machines exist, we can equivalently say: if P==NP then there exists a deterministic program that takes a description of a non-deterministic TM and an input string, such that if the non-deterministic TM halts in polynomial time, so does the deterministic algorithm (with the same answer). (The standard proof of the Cook-Levin theorem assumes that you actually have a polynomial bound on the number of time steps, rather than simply being assured that one exists. This is a technical detail that can be worked around by e.g. doubling the number of steps exponentially until you detect termination.)
- BrainInAJar 11y ago
  primality testing is a poor example. PRIMES is in P. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...
  - _asummers 11y ago
    Even factoring would be a poor example, given that it has never been shown to be NP-complete.
    - BrainInAJar 11y ago
      It would be very surprising if it were, since it's also in co-NP. The other problems in NP intersect co-NP are all in P. It's not at all unlikely, and a lot of evidence points towards, that integer factorization is in P.
1arity 11y ago
"We can't find a polynomial time algorithm" !==> "No such algorithm exists" The height of arrogance. For these limited human minds, in limited time to declare that their effort has already exhausted all possibilities. The very core of ridiculousness.
- MarkPNeyer 11y ago
  There is _so much more_ to the suspicion that P doesn't equal NP than just this. The curiously repeated patterns in the boundary that seem to exist everhwyere you go. It's like looking at a distant planet through a telescope, and seeing what _appears to be_ an island in a lake, but _might_ be a peninsula. Every place the island bulges out, the land around it also bulges out. Every place there's a shallow in the island, the land on the other side also comes into meet it. So its' either a weird, jagged-shaped island in the middle of a lake, with an equally weird jagged coastline around it - or else in one of the places, but _only_ only of those places, the coastline touches the shore. My guess is that you haven't studied this problem nearly as much as the complexity theorists who suspect P doesn't equal NP, and you feel like you know better. Thats it's own kind of arrogance. Believe me, I was there, too.
  - Sniffnoy 11y ago
    Scott Aaronson has some good posts on the matter: http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=1720 http://www.scottaaronson.com/blog/?p=1720 (The second of these talks a lot about the matter of the boundary that you mention.)
- javert 11y ago
  Except nobody is saying that. Every computer scientist acknowledges that we have not proven P!=NP. I would be delighted to see either P!=NP or P=NP proven. I have devoted 0% of my career to this question, so it does not stand to embarass me. I suppose this is the case for the vast majority of people who suspect P!=NP (myself included). There are only a few people that stand to really be embarassed by a proof. And among those, probably even fewer actually care enough to be embarassed.
teraflop 11y ago
How is believing that P!=NP any more "defeatist" than believing P==NP? Or are you somehow under the impression that computer scientists aren't actively working on proving that P!=NP?
- 1arity 11y ago
  Because believing P != NP means, and is frequently invoked as a justification that : 1) we no longer have to keep looking for a P time algo, and 2) ah, that's why we couldn't solve that -- because we proved it is in NP, and P isn't equal to that, so we can chalk our failure to solve it up to that. P == NP is leaving the possibility open, which, by absence of a proof to the contrary __is__ open, that we __can__ find an algorithm. That is not defeatist. That is let's keep going. Let's make it. What you believe is your choice. To me it seems a waste of good brains to see so much CS talent giving themselves an easy out like this. I know where I stand and I'll keep working on the things I care about. People can choose to be part of the future, or left in the dust of those who walk ahead. My view is -- all those really hard unsolved problems? That's where everyone should be focussing. Anything else is just nibbling around the edges, it's just a cowardly hedge. A waste. The incentives have become toxic to the creation of brave innovation. People are satisfied with too little.
  - MarkPNeyer 11y ago
    consider a world in which P equals NP. What does this mean? All internet crypto could break, almost immediately if a valid a solution were found. What does this do to society? A philosophical class on skeptisim, or a class on software security - they both lead to the same conclusion, that the outside world is a potentially terrifying place. Identities can give rise to trust in something out side of you - but it's impossible to form identities without a "one way" computational mechanism like P != NP. Our ability to say "You know me by my words; you can recognize my language, but cant speak it yourself" - that doesn't work any more if P = NP. The ability to say "yes, that's MarkPNeyer saying that" is the same as the ability to speak with my voice. Now consider a world in which P does not equal NP. - it suggests that a single expert is not as powerful as large groups; a single person acting alone is like a single turing machine. A quantum computer is sort of like society - everyone tries their own way, and if someone finds a solution that works, it is made obvious to everyone else through their success. - it provides a meaningful basis for identity. Someone can publish cryptogrpahically signed statements attesting to a believe, and we can trust that it's the same person (or group of people) operating behind that identity, becuase of the meanignful difference between verifying a truth (this is the same person who posted these keys) and finding a solution (find the private key which leads to posting these two things.) Now, of course the "world I want to live in" does't directly suggest anything one way or the other - I'm just hoping you can stop seeing "P != NP" as being defeatist - if anything, it's a wonderful result, from a philosophical perspective, because it implies a world rich, full of diversity, with meaningful notions of identity. If P = NP, the polynomial time hierarchy collapses - and there's a good chance society does as well.
MarkPNeyer 11y ago
i spent years thinking about p vs np, under the same intution you have - i figured p must equal np. i even had it on my license plate: http://s3.neyer.me/pnp.jpg http://s3.neyer.me/pnp.jpg after nightmares involving np complete problems, i finally started considering that p didn't equal np, and suddenly the world made much more sense. https://www.youtube.com/watch?v=dUD9fDxiWKs https://www.youtube.com/watch?v=dUD9fDxiWKs
- 1arity 11y ago
  I hope sometime you come back to the light. Stay strong.
  - MarkPNeyer 11y ago
    see my response here: https://news.ycombinator.com/item?id=10074890 https://news.ycombinator.com/item?id=10074890 a world where P = NP is a much darker world.
    - 1arity 11y ago
      Dude, with all due respect, that's what the church said when the possibility was raised of the Earth not being the centre of the universe. "We cannae conceive how it can be bearable to be so" !==> "It can not be so"
- javert 11y ago
  That license plate is just awesome.
- darkmighty 11y ago
  Nice talk! I'm unsure about the excessive use of analogies. If you don't have a very precise isomorphism it can be unproductive, but the ones you've shown are cool. About your turnover on the PvsNP problem, did that have to do with realizing that approximations can be quite good for practical purposes? What's the current state of approximations in the field? I find it interesting because the only application I know where approximations are complete garbage is cryptography, or "adversarial" applications; is that right? In that case P!=NP yields the best of both words: we can build trapdoor functions for adversarial systems but still solve optimization problems well. I find that picture very convincing for some reason (exact solutions are hard, usable approximations are easy).
prtzl 11y ago
Plenty of people have tried to prove that P != NP, so far unsuccessfully. Do you think those people want to believe that P == NP so they can feel better?
1arity 11y ago
Why is there such a strong reaction to this? For the very reasons identified. People want it to be true, without proof, because believing it is true serves a psychological need that provides a fake pay off. It's not "your fault" you didn't make progress in that algorithm, because "the universe" conspired against you and "P != NP", you're off the hook. Getting off the hook like that is so much easier than facing your own responsibility. I understand it's very compelling to believe this for that reason, and yet, to do so doesn't work to actually make progress. I understand the psychology. People will fight this to the end to preserve their sense of zero responsibility, to shelter their ego. So much invested, so many layers of justifying narrative, already deposited. I'm not saying it's right or wrong what you choose to believe. I don't think you need to feel bad about it. You can choose to live your life however you want. If you want to believe P != NP without proof, you're just not someone who is mentally equipped to create innovations in that space. Does that make you bad? No, it's just your choice. You already made that choice. No need to deceive yourself about it. Can you really feel an absence of shame however, trying to talk other people out of it? I guess that is what I am campaigning for. Believe whatever you want, you've already made your choice. When that young student comes to you, and you try to talk her or him out of pursuing this to preserve the narrative you've already subscribed to yourself, that doesn't work. So if you are aware of how it's your belief, maybe you'll give them space for their belief. That awareness, and awareness toward others.
- MarkPNeyer 11y ago
  I spent years working towards a solution, to prove P = NP. I was miserable, isolated and alone - because I was focused on mathematical symbols instead of the people around me. When I started considering that P didn't equal NP, it was the same time that I started thinking about and seriously considering the idea that there was somethign more powerful about groups of people than a single intellect. A single turing machine is like a single mind; a quantum computer is like the thoughts of an entire society. If P = NP, it suggests that smartest guy in the room always wins. If P doesn't equal NP - it means a group can overpower a single smart person. There's a lot of ego in thinking the former.
  - 1arity 11y ago
vernie 11y ago
Are you a football coach or something? Should we be giving it 110%?
VLM 11y ago
I'd rephrase it as It's a harmless human illogicality at the heart of math. True math is often very beautiful. Being unable to prove something one way or another is seen as very ugly. Unfortunately it might very well be unprovable and thus a permanent pimple on the face of mathematics. So mathematicians are going to get all worked up about it for eternity even if it is unsolvable because it is ugly not to be solved on way or another. Of course unsolvable problems have a strange way of getting solved in weird ways after a zillion combined human lifetimes of effort. It doesn't seem unrealistic that a math problem can be defined that cannot be proven. Someone named Godel had a lot to say on the topic. Turing too. Mostly they get misquoted, I see no reason to add to the existing corpus of misquoting. I could add a "funny" analogy to some theoretical physics topics here too. Physics is weaker in that the physical world is simpler than the imaginative world so its more likely physics will eventually stop, and stops are invariably at a rather ugly point. Some might say it has already stopped. But at some point it will stop, probably before math hits its stopping point.
ColinWright 11y ago
You write your comment, which I will reply to shortly, and then upon receiving lots of downvotes you said: > Why is there such a strong reaction to this? > For the very reasons identified. I believe that not to be the case. Let me explain just some of the reasons why I believe you are getting a strong negative reaction. > It's cool that this paper exists as a > counterpoint to the pervasive culture > of defeat around P == NP. I have no idea why you believe there is any "culture of defeat" about this. All the people I know who are working on, in, near, or around this area are just looking for the truth. They want to know whether P==NP or P!=NP, and they are looking to discover what actually is the case. It may even be unprovable, and some of them are seriously investigating that. There is no air of defeat, and I don't know why you think there is. You then say: > People want to believe P != NP so they > feel better about how they failed to > prove it. Really? Then why don't they want to believe that P==NP because they have failed to prove that P!=NP? You can't have it both ways. No, really, you can't. And people aren't in despair over not having proved it either way. It's evidence that this is a hard problem, and then the small amount of progress that has been made is genuinely encouraging. Showing that different approaches cannot, under certain generous assumptions, be made to work is real progress. Your claim here just appears to be nonsense. > This is ridiculous and doesn't help > advance the cause to solve it. It's > an illogicality at the heart of the > CS establishment, ... It might be, if only it existed. But it doesn't. > ... everyone is "confident" P != NP, That's not the case. There is a significant minority who believe that P==NP, there is a significant minority that believes it's undecidable, and those who do believe it certainly are nowhere near 100% certain. > ... with no proof, simply so they can > move on to other things. And yet they continue to work on it. Odd definition of "moving on". > What happened to backbone, determination > and persistence? > Their confidence in impossibility smells > of self-justification of failure, and fear. It is impossible to find two positive whole square numbers that differ by a factor of two. This impossibility hasn't disturbed anyone for a long time. It's impossible to find positive whole numbers x, y, z, and n, greater than 2, such that x^n+y^n=z^n. This impossibility has led not to a sense of failure, but a sense of triumph! Your assertions here are strange, and don't seem to reflect reality at all. > And the irrational "culture of belief" > ( without proof ) is the very antithesis > of good science. Then it's a good job that it's non-existent (in the form you seem to be describing) in mathematics. Or in science. People do have an intuition about what's probably going to turn out to be true, but what you describe is bizarre, and unrecognisable to me. Hence my downvote. > Your downvote makes you complicit to > this culture of defeat. That's simply wrong.
deleted 11y ago
[deleted]

by 1arity 11y ago

deleted 11y ago

[deleted]

chpatrick 11y ago

Well, it would also be very strange if P=NP because you could use algorithms like this in polynomial time: bool isComposite(n) { guess a number d magically if (n % d == 0) { return true; } else { fail; } }

mikeash 11y ago
P = NP just means that there exist some polynomial-time algorithm that's able to solve that problem. It doesn't mean that you can take that pseudocode and run it directly in polynomial time.
- teraflop 11y ago
  Actually, it kind of does. If P==NP, then any problem in NP is solvable in polynomial time -- including efficient simulation of a non-deterministic Turing machine that supports "guessing correctly" as a primitive operation. That's why the P=?NP problem has such far-reaching implications, and one reason why P==NP is generally believed to be false.
  - 1arity 11y ago
    What's the reduction from 3-SAT to "guessing correctly"?
    - teraflop 11y ago
      The original reduction was given by the well-known Cook-Levin theorem. It's really the existence of this theorem that motivated the entire study of NP-complete problems in the first place. Basically, you can unroll the execution of a non-deterministic Turing machine along the time axis, using separate variables to represent the state of the machine at each time step. All of the rules that govern the Turing machine's execution can be encoded as Boolean formulas, resulting in one giant formula such that the formula is satisfiable iff there is an assignment of variables corresponding to a valid execution. Adding non-determinism (the "guessing") is easy; you just leave particular variables unconstrained. If the original machine runs in polynomial time, then the number of variables and clauses is also polynomial. And of course there's a straightforward polynomial reduction from SAT to 3-SAT. No offense, but if you don't already know about this, it's kind of ironic that you're the one claiming CS researchers are "arrogant" for their beliefs about P=?NP.
  - mikeash 11y ago
    Is efficient simulation of a nondeterministic Turing machine in NP? I don't see how that could be the case. These are decision problems, where you pose a yes/no question, and you get an answer. If a decision problem is in P, then you get your yes/no answer in polynomial time when run on a normal Turing machine. If it's in NP, then you get your yes/no answer in polynomial time when run on a nondeterministic Turing machine. What would be the yes/no answer for "simulation of a non-deterministic Turing machine"? If it's just "the yes/no answer provided by whatever that Turing machine runs" then that problem is clearly not in NP, since you could easily have some code that takes more than polynomial time. Can you restrict it to "the yes/no answer provided by whatever that Turing machine runs, provided that it runs in polynomial time"?
    - teraflop 11y ago
      Well, that comes back to the definition of NP. A problem is in NP iff it is solvable by a non-deterministic Turing machine that is guaranteed to run in polynomial time. If such a machine exists, and P==NP, then the problem is also solvable by a deterministic Turing machine in polynomial time. Strictly speaking, the proof assumes a particular Turing machine. But since universal Turing machines exist, we can equivalently say: if P==NP then there exists a deterministic program that takes a description of a non-deterministic TM and an input string, such that if the non-deterministic TM halts in polynomial time, so does the deterministic algorithm (with the same answer). (The standard proof of the Cook-Levin theorem assumes that you actually have a polynomial bound on the number of time steps, rather than simply being assured that one exists. This is a technical detail that can be worked around by e.g. doubling the number of steps exponentially until you detect termination.)
BrainInAJar 11y ago
primality testing is a poor example. PRIMES is in P. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...
- _asummers 11y ago
  Even factoring would be a poor example, given that it has never been shown to be NP-complete.
  - BrainInAJar 11y ago
    It would be very surprising if it were, since it's also in co-NP. The other problems in NP intersect co-NP are all in P. It's not at all unlikely, and a lot of evidence points towards, that integer factorization is in P.

1arity 11y ago

"We can't find a polynomial time algorithm" !==> "No such algorithm exists" The height of arrogance. For these limited human minds, in limited time to declare that their effort has already exhausted all possibilities. The very core of ridiculousness.

MarkPNeyer 11y ago
There is _so much more_ to the suspicion that P doesn't equal NP than just this. The curiously repeated patterns in the boundary that seem to exist everhwyere you go. It's like looking at a distant planet through a telescope, and seeing what _appears to be_ an island in a lake, but _might_ be a peninsula. Every place the island bulges out, the land around it also bulges out. Every place there's a shallow in the island, the land on the other side also comes into meet it. So its' either a weird, jagged-shaped island in the middle of a lake, with an equally weird jagged coastline around it - or else in one of the places, but _only_ only of those places, the coastline touches the shore. My guess is that you haven't studied this problem nearly as much as the complexity theorists who suspect P doesn't equal NP, and you feel like you know better. Thats it's own kind of arrogance. Believe me, I was there, too.
- Sniffnoy 11y ago
  Scott Aaronson has some good posts on the matter: http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=1720 http://www.scottaaronson.com/blog/?p=1720 (The second of these talks a lot about the matter of the boundary that you mention.)
javert 11y ago
Except nobody is saying that. Every computer scientist acknowledges that we have not proven P!=NP. I would be delighted to see either P!=NP or P=NP proven. I have devoted 0% of my career to this question, so it does not stand to embarass me. I suppose this is the case for the vast majority of people who suspect P!=NP (myself included). There are only a few people that stand to really be embarassed by a proof. And among those, probably even fewer actually care enough to be embarassed.

teraflop 11y ago

How is believing that P!=NP any more "defeatist" than believing P==NP? Or are you somehow under the impression that computer scientists aren't actively working on proving that P!=NP?

1arity 11y ago
Because believing P != NP means, and is frequently invoked as a justification that : 1) we no longer have to keep looking for a P time algo, and 2) ah, that's why we couldn't solve that -- because we proved it is in NP, and P isn't equal to that, so we can chalk our failure to solve it up to that. P == NP is leaving the possibility open, which, by absence of a proof to the contrary __is__ open, that we __can__ find an algorithm. That is not defeatist. That is let's keep going. Let's make it. What you believe is your choice. To me it seems a waste of good brains to see so much CS talent giving themselves an easy out like this. I know where I stand and I'll keep working on the things I care about. People can choose to be part of the future, or left in the dust of those who walk ahead. My view is -- all those really hard unsolved problems? That's where everyone should be focussing. Anything else is just nibbling around the edges, it's just a cowardly hedge. A waste. The incentives have become toxic to the creation of brave innovation. People are satisfied with too little.
- MarkPNeyer 11y ago
  consider a world in which P equals NP. What does this mean? All internet crypto could break, almost immediately if a valid a solution were found. What does this do to society? A philosophical class on skeptisim, or a class on software security - they both lead to the same conclusion, that the outside world is a potentially terrifying place. Identities can give rise to trust in something out side of you - but it's impossible to form identities without a "one way" computational mechanism like P != NP. Our ability to say "You know me by my words; you can recognize my language, but cant speak it yourself" - that doesn't work any more if P = NP. The ability to say "yes, that's MarkPNeyer saying that" is the same as the ability to speak with my voice. Now consider a world in which P does not equal NP. - it suggests that a single expert is not as powerful as large groups; a single person acting alone is like a single turing machine. A quantum computer is sort of like society - everyone tries their own way, and if someone finds a solution that works, it is made obvious to everyone else through their success. - it provides a meaningful basis for identity. Someone can publish cryptogrpahically signed statements attesting to a believe, and we can trust that it's the same person (or group of people) operating behind that identity, becuase of the meanignful difference between verifying a truth (this is the same person who posted these keys) and finding a solution (find the private key which leads to posting these two things.) Now, of course the "world I want to live in" does't directly suggest anything one way or the other - I'm just hoping you can stop seeing "P != NP" as being defeatist - if anything, it's a wonderful result, from a philosophical perspective, because it implies a world rich, full of diversity, with meaningful notions of identity. If P = NP, the polynomial time hierarchy collapses - and there's a good chance society does as well.

MarkPNeyer 11y ago

i spent years thinking about p vs np, under the same intution you have - i figured p must equal np. i even had it on my license plate: http://s3.neyer.me/pnp.jpg http://s3.neyer.me/pnp.jpg after nightmares involving np complete problems, i finally started considering that p didn't equal np, and suddenly the world made much more sense. https://www.youtube.com/watch?v=dUD9fDxiWKs https://www.youtube.com/watch?v=dUD9fDxiWKs

1arity 11y ago
I hope sometime you come back to the light. Stay strong.
- MarkPNeyer 11y ago
  see my response here: https://news.ycombinator.com/item?id=10074890 https://news.ycombinator.com/item?id=10074890 a world where P = NP is a much darker world.
  - 1arity 11y ago
    Dude, with all due respect, that's what the church said when the possibility was raised of the Earth not being the centre of the universe. "We cannae conceive how it can be bearable to be so" !==> "It can not be so"
javert 11y ago
That license plate is just awesome.
darkmighty 11y ago
Nice talk! I'm unsure about the excessive use of analogies. If you don't have a very precise isomorphism it can be unproductive, but the ones you've shown are cool. About your turnover on the PvsNP problem, did that have to do with realizing that approximations can be quite good for practical purposes? What's the current state of approximations in the field? I find it interesting because the only application I know where approximations are complete garbage is cryptography, or "adversarial" applications; is that right? In that case P!=NP yields the best of both words: we can build trapdoor functions for adversarial systems but still solve optimization problems well. I find that picture very convincing for some reason (exact solutions are hard, usable approximations are easy).

prtzl 11y ago

Plenty of people have tried to prove that P != NP, so far unsuccessfully. Do you think those people want to believe that P == NP so they can feel better?

1arity 11y ago

Why is there such a strong reaction to this? For the very reasons identified. People want it to be true, without proof, because believing it is true serves a psychological need that provides a fake pay off. It's not "your fault" you didn't make progress in that algorithm, because "the universe" conspired against you and "P != NP", you're off the hook. Getting off the hook like that is so much easier than facing your own responsibility. I understand it's very compelling to believe this for that reason, and yet, to do so doesn't work to actually make progress. I understand the psychology. People will fight this to the end to preserve their sense of zero responsibility, to shelter their ego. So much invested, so many layers of justifying narrative, already deposited. I'm not saying it's right or wrong what you choose to believe. I don't think you need to feel bad about it. You can choose to live your life however you want. If you want to believe P != NP without proof, you're just not someone who is mentally equipped to create innovations in that space. Does that make you bad? No, it's just your choice. You already made that choice. No need to deceive yourself about it. Can you really feel an absence of shame however, trying to talk other people out of it? I guess that is what I am campaigning for. Believe whatever you want, you've already made your choice. When that young student comes to you, and you try to talk her or him out of pursuing this to preserve the narrative you've already subscribed to yourself, that doesn't work. So if you are aware of how it's your belief, maybe you'll give them space for their belief. That awareness, and awareness toward others.

MarkPNeyer 11y ago
I spent years working towards a solution, to prove P = NP. I was miserable, isolated and alone - because I was focused on mathematical symbols instead of the people around me. When I started considering that P didn't equal NP, it was the same time that I started thinking about and seriously considering the idea that there was somethign more powerful about groups of people than a single intellect. A single turing machine is like a single mind; a quantum computer is like the thoughts of an entire society. If P = NP, it suggests that smartest guy in the room always wins. If P doesn't equal NP - it means a group can overpower a single smart person. There's a lot of ego in thinking the former.
- 1arity 11y ago

vernie 11y ago

Are you a football coach or something? Should we be giving it 110%?

VLM 11y ago

I'd rephrase it as It's a harmless human illogicality at the heart of math. True math is often very beautiful. Being unable to prove something one way or another is seen as very ugly. Unfortunately it might very well be unprovable and thus a permanent pimple on the face of mathematics. So mathematicians are going to get all worked up about it for eternity even if it is unsolvable because it is ugly not to be solved on way or another. Of course unsolvable problems have a strange way of getting solved in weird ways after a zillion combined human lifetimes of effort. It doesn't seem unrealistic that a math problem can be defined that cannot be proven. Someone named Godel had a lot to say on the topic. Turing too. Mostly they get misquoted, I see no reason to add to the existing corpus of misquoting. I could add a "funny" analogy to some theoretical physics topics here too. Physics is weaker in that the physical world is simpler than the imaginative world so its more likely physics will eventually stop, and stops are invariably at a rather ugly point. Some might say it has already stopped. But at some point it will stop, probably before math hits its stopping point.

ColinWright 11y ago

You write your comment, which I will reply to shortly, and then upon receiving lots of downvotes you said: > Why is there such a strong reaction to this? > For the very reasons identified. I believe that not to be the case. Let me explain just some of the reasons why I believe you are getting a strong negative reaction. > It's cool that this paper exists as a > counterpoint to the pervasive culture > of defeat around P == NP. I have no idea why you believe there is any "culture of defeat" about this. All the people I know who are working on, in, near, or around this area are just looking for the truth. They want to know whether P==NP or P!=NP, and they are looking to discover what actually is the case. It may even be unprovable, and some of them are seriously investigating that. There is no air of defeat, and I don't know why you think there is. You then say: > People want to believe P != NP so they > feel better about how they failed to > prove it. Really? Then why don't they want to believe that P==NP because they have failed to prove that P!=NP? You can't have it both ways. No, really, you can't. And people aren't in despair over not having proved it either way. It's evidence that this is a hard problem, and then the small amount of progress that has been made is genuinely encouraging. Showing that different approaches cannot, under certain generous assumptions, be made to work is real progress. Your claim here just appears to be nonsense. > This is ridiculous and doesn't help > advance the cause to solve it. It's > an illogicality at the heart of the > CS establishment, ... It might be, if only it existed. But it doesn't. > ... everyone is "confident" P != NP, That's not the case. There is a significant minority who believe that P==NP, there is a significant minority that believes it's undecidable, and those who do believe it certainly are nowhere near 100% certain. > ... with no proof, simply so they can > move on to other things. And yet they continue to work on it. Odd definition of "moving on". > What happened to backbone, determination > and persistence? > Their confidence in impossibility smells > of self-justification of failure, and fear. It is impossible to find two positive whole square numbers that differ by a factor of two. This impossibility hasn't disturbed anyone for a long time. It's impossible to find positive whole numbers x, y, z, and n, greater than 2, such that x^n+y^n=z^n. This impossibility has led not to a sense of failure, but a sense of triumph! Your assertions here are strange, and don't seem to reflect reality at all. > And the irrational "culture of belief" > ( without proof ) is the very antithesis > of good science. Then it's a good job that it's non-existent (in the form you seem to be describing) in mathematics. Or in science. People do have an intuition about what's probably going to turn out to be true, but what you describe is bizarre, and unrecognisable to me. Hence my downvote. > Your downvote makes you complicit to > this culture of defeat. That's simply wrong.

deleted 11y ago

[deleted]