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.
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.
Depends on what kind of tools you're talking about. For instance, if P==NP then there can be no such thing as a secure digital signature algorithm; anybody who can efficiently verify a signature can also forge one. (Making the usual simplification that "efficient" == "polynomial-time", that is.)
Except that line of reasoning is completely incorrect -- both in its understanding of the problem, and in its understanding of the current state of the field. For one, most "interesting" problems are in NP, not the least of reasons being P is undeniably a subset of NP. Here's a nice Venn-diagram-like thing on wikipedia:
https://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard....
So if you prove your solution is NP, you don't get to say "Whelp, it's impossible!" and move on. That would be like saying "We proved that you could build this machine if we had a perpetual motion engine, and those are probably impossible, so the machine can't be built." If, on the other hand, you prove that your machine could be used to build a "perpetual motion engine" (i.e. a poly-time solution to the new problem could be used to construct a poly-time solution to an NP-complete problem), then that might be a good time to admit it's almost certainly impossible to build it. But again, that's not where the field lets it rest.
NP-complete problems have very direct applications to many, many real world problems we try to solve. The state of the art in these solutions is not "It will never be polynomial time, so we don't try." Research papers are constantly churning out new, faster algorithms for NP-complete problems -- they're just not poly-time algorithms. For example, k-sat is the most textbook example of an NP-complete problem, and there is an annual competition regarding the latest algorithms for solving it: http://www.satcompetition.org/ In fact, working on this stuff isn't exactly the smallest field within CS, and a novel solution yielding better performance does very well to an academic reputation, and there are definitely people trying.
So rest assured, in the unlikely event that some new techniques arise that allow the creation of poly-time solutions to NP-complete problems, they will not go unnoticed. But thanks for calling us cowards.
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.
i even had it on my license plate:
after nightmares involving np complete problems, i finally started considering that p didn't equal np, and suddenly the world made much more sense.
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).
a world where P = NP is a much darker world.
"We cannae conceive how it can be bearable to be so" !==> "It can not be so"
> Why is there such a strong reaction to this?
> For the very reasons identified.
> It's cool that this paper exists as a
> counterpoint to the pervasive culture
> of defeat around P == NP.
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.
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, ...
> ... 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.
Hence my downvote.
> Your downvote makes you complicit to
> this culture of defeat.
bool isComposite(n) {
guess a number d magically
if (n % d == 0) {
return true;
} else {
fail;
}
}That's why the P=?NP problem has such far-reaching implications, and one reason why P==NP is generally believed to be false.
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"?
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.)
Just to make sure I got this right, the basic idea is: simulate the non-deterministic Turing machine using boolean variables, with unconstrained variables for the nondeterministic part. Sort of a symbolic execution on a Turing machine. Convert the simulation to a boolean expression. Convert the boolean expression to 3-SAT form. Put 3-SAT problem into your magical P==NP machine and get an answer out. You've now found the answer given by the nondeterministic Turing machine in polynomial time, if the original would indeed run in polynomial time.
The parts that are "by definition" are:
* the set of programs involving steps like "guess magically" correspond to the ones that can be implemented with at most polynomial slowdown by a non-deterministic Turing machine (this is hand-wavy, but then again we're talking about pseudocode; it's possible to state it more precisely)
* if such an algorithm runs in polynomial time, then it's in NP (by the definition of NP)
* ...so it can be reduced to an instance of any NP-complete problem (by the definition of NP-complete)
* ...and if P=NP then there exists a deterministic, polynomial-time algorithm to solve the problem
The parts that require actual proofs are:
* the fact that the "well-known" examples of NP-complete problems like 3-SAT, TSP, and so on actually correspond to the formal definition of NP. These proofs ultimately reduce to the Cook-Levin theorem, or something similar in spirit.
* the fact that if any problem in NP has a deterministic polynomial-time algorithm, then there is one algorithm that can solve all NP problems in polynomial time. This relies on the existence of universal Turing machines that have at most a polynomial slowdown.
It's likely there are other details that I'm forgetting, but that's the gist of the argument.
And I don't think you were too terse. Thankfully HN makes it easy to see sub-replies to your comments so I saw your reply to 1arity, which was exactly what I needed, and your reply to me capped it off.
Yes, essentially. You stop the simulation after T(n) steps, where T is a polynomial function that depends on the simulation, and reject the input if you haven't accepted by that point. It's clearly in NP as a result.
As a side question (sorry probably newbie question), why can't we just use nondeterministic turing machines to achieve what we want? (i.e. introduce optional randomness at the circuit level)
Another way of thinking about it is as pure magic. If there is a number that's a match, then that number comes out of the "guess" function somehow.
As for why we can't use a nondeterministic Turing machine to achieve what we want, it's because nobody knows how to build one. They're the computing equivalent of a frictionless pulley or a mathematical point: a useful abstraction, but not something you can actually construct. If anyone ever figures out how to send information back in time then it may be possible, but absent that we're stuck with the regular kind of Turing machine.
Given a deterministic machine (let's say a Turing machine, but the same concept can be applied to more restrictive settings like FSMs or pushdown automata) there's an often-unstated assumption on how we use the machine to solve a problem. We let the machine run until it halts, and then we look at the final state. For decision problems, we usually define a special "accepting" state and say the answer is YES iff the machine halts in that state.
For non-deterministic machines, we allow multiple possible transitions from any given state. So "look at the final state" is no longer meaningful, because now there are many possible sequences of states the machine could follow. Instead, we say that the machine returns an answer of YES iff there is some allowed sequence of transitions that ends in the accepting state.
This is an entirely theoretical concept; the answer to "why don't we just solve problems using nondeterministic TMs?" is "because we have no reason to think it's physically possible for them to exist." (You can simulate them -- just keep track of all of the possible execution paths and check them one-by-one. But then any notion of efficiency goes out the window, because the number of paths grows exponentially, causing the amount of work required to simulate a single timestep to grow without bound.)
If you think about it the right way, this formal definition captures what it means to say that the power of a nondeterministic machine is the ability to "guess correctly". In the algorithm described above, if there exists some d that divides n, then d is composite. We don't know what the value of d is, but if we had a nondeterministic machine, we could just explore all possible choices. If one of them turns out to work, then that path ends in an accepting state, so the machine returns YES. Maybe the "guess magically" function is implemented as:
value = 0
while (value < n) {
nondeterministically {
return value
} or {
value++
}
}
Btw, is there a class that is actually "Turing machines with randomness in polynomial time" and is it more powerful than "Turing machines in polynomial time"?
ZPP contains problems for which the answer is guaranteed to be correct, and the machine halts in expected polynomial time -- the so-called "Las Vegas" algorithms. And then there's BPP, containing algorithms which always run in polynomial time but whose outputs have a constant, bounded probability of being wrong -- the "Monte Carlo" algorithms.
Currently, we know that P ⊆ ZPP ⊆ BPP, but we haven't yet proved whether or not any of those classes are equal to each other. However, there's apparently mounting evidence -- most of which goes over my head -- that in fact P=BPP; in other words, any randomized algorithm can be "derandomized" with the use of a sufficiently strong pseudorandom number generator.
( P!=NP => BPP=P => P=BPP!=NP ?)
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.
http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...
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.
Computer scientists won't be popping champagne if a proof for P = NP or P != NP is found. If P = NP, then the crypto community will have to rethink some of its fundamental assertions. If P != NP, then we can continue along. No respectable computer scientist would ever discourage someone from considering P = NP, but scientific evidence should guide a reasonable hypothesis rather than flowery language.
Let me make it clear that I'm not trying to bash your viewpoint, this is more of a general thing you should understand - scientific direction is guided by empirical evidence and not by human beliefs. When you guide scientific intuition with human intuition, then your reasoning is easily misguided by papers like this one, where human intuition takes the place of scientific rigor.
it's condescending towards the majority intuition with no reasoning about the actual issue whatsoever?
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.
You had a problem with working on this. You found a solution to that. I hear that.
The solution you found that worked for you has no bearing on a solution of the problem you abandoned.
They say perspective is 80 IQ points. Maybe no one has had the perspective that works on it yet?
In any case, if you are going to be someone who solves P == NP, you need to also be someone capable of solving the "you as a person working on P == NP" problem, the meta problem.
You got to take care of yourself, so you can take care of the problem. If you don't do one, how can you do the other?
The video gamer can't run the marathon until he trains. Even if you have the brain for this, you can't do it until you can sustain your effort. It's like an elite sport.
and to be honest, i haven't ruled out the possibility that P = NP.
i just think those who suspect it does have many strong reasons for suspecting it.
but then, the michelson-morely experiment was also expected to succeed, and didn't...
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.
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.
http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=1720
(The second of these talks a lot about the matter of the boundary that you mention.)
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.
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.