An Argument for P=NP (2005) [pdf]
kryten.mm.rpi.edu
kryten.mm.rpi.edu
For example, the Steiner Tree problem (STP) is
known to be NP-complete ... Nonetheless, a simple
physical process (termed an analog computation)
can apparently solve it quickly.
This is at the top of page 2, and it doesn't bode at all well. Section 3 of Aaronson's paper[0] discusses this explicitly, and comes to the conclusion that, not to put too fine a point on it, it doesn't work.
In essence, looks like complete nonsense to me.
For example, take "spaghetti sort." This is a weird physical sorting algorithm where you represent each number to be sorted as a physical strand of uncooked spaghetti of corresponding length. To perform the sort, you grab the spaghetti in a bundle and place it on a table so the bottom of each spaghetti strand is on the table. Then you put your other hand on top, find the longest strand, and pull it out. Repeat this process once for each strand, and you then have all the numbers in order.
This is described as a "linear time" algorithm because you perform the same procedure once per number, so it's clearly O(n). It's obviously impractical for real-world use, but if you had some utterly ridiculous quantity of numbers, maybe it could be the best way!
But of course this ignores important factors. For example, the radius of the bundle will increase with the square root of the number of strands present within it. Whatever you use to select and retrieve the longest strand must move at some finite speed to traverse this distance, which means that the actual running time is O(n^1.5), substantially worse than the theoretical O(n log n) limit!
Another factor that is often ignored is the fact that analog systems don't actually have infinite precision. If you look at their actual (or even theoretical) precision and convert that to bits, it's not all that many! Lots of analog solutions can look extremely clever and quick, until you realize that it's just solving the problem for a 28-bit number, or whatever.
Here's another variation: arrange the sticks in a line. Have a pole scan the sticks from the top, and when the pole is impeded, record it's height. You've just computed max(a1,...,aN) in O(1) time?! (disproving is left as an exercise -- note you can even assume the pole is weightless and infinite!)
Relativity tells us that disturbances in the pole cannot move faster than the speed of light. Therefore the time it takes to find out that your pole hit something is O(n), since the location of the tallest element will be on average halfway down your line.
Of course, there's the much more obvious problem that "arrange the sticks in a line" requires manipulating each stick, and is thus O(n)!
[1] https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...
But I agree that the argument is badly flawed(1). The soap bubble STP machine and and similar machines are probabilistic solvers. They are doing stochastic gradient descent from initial conditions, with the usual lack of global optimal convergence guarantee.
(1) It may be satire. Does anyone know if this is so?
(Also, blowing is not guaranteed to move the answer towards the global solution. Even if you can quickly determine that an answer is not optimal and blow it around, you could just spend forever going in circles.)
The paper is a good read, by the way. Everyone here should skip the posted article, and read Aaronson's.
I think the idea of alternate physical systems doing computation is really fun. I personally have a throbbing heart-on for cellular automata, specifically Rule 110 and inspired by Greg Egan's "Permutation City". But that's SF. But that's just emotional attachment.
That’s easy. The NTM is just a condensed representation of a DTM, and in each case, the machine encodes an algorithm for whatever NP problem you are working. “Guessing correctly” has no bearing on NP, and it’s not a scary or impossible property that it works for people to believe implies P == NP is false. “Guessing correctly” ( otherwise known as branching ) is simply a property of the NTM occupying more than one subsequent state. As long as you construct an algorithm such that the NTM branches on its guesses in P time ( or equivalently the DTM is P size), then you have the P time algorithm. Pretending a valid reason for P == NP being “widely believed to be false” because there would then exist “an NTM that supports guessing correctly as a primitive operation”, as if this should be somehow intuitively magical and impossible, is obfuscation, “guessing correctly” has nothing to do with NP and makes no problem harder or easier. “Guessing correctly” won’t make a shit algorithm good ( it’s not like an oracle in a quantum algorithm like Shor’s ), it’s just another way of describing a NTM. All you need to worry about is making that P time algorithm for some NP problem. Whether you want to implement that as a DTM or a NTM, is totally up to you. If it’s a P time algorithm it’s still a P time algorithm. I can make an EXP time algorithm in a NTM too if I like. “Guessing correctly” is not some magical speedup equivalent to P == NP. Too suggest that, or imply that, by suggesting that such a machine would somehow be magical is either the result of someone who doesn’t understand this, or someone who is choosing to obfuscate this. So either you don’t understand it, and you are pretending that you do. Or you do understand it and you are needlessly fabricating to try to argue for P !== NP, simply revealing how tenuous you fear the arguments are, and how deeply you lack any substantive ones that you must fabricate them. Your language is an attempt to obfuscate and incorrectly attempt to confuse people who don’t understand. If you really know this space, doing that is just balderdash. Well played.
yes exactly.
you have perfectly summed up how its percieved by those in the defeatist culture around P can not be == NP, and this really goes to the heart of what is inefficient and not working here.
and that is especially what im talking about when I speak about the psychology of compelling pay offs for believing this, and the strong attempts at defensiveness when its being considered that the majority response doesnt work.
NP defeatists can not stand the feeling they percieve of being condescended to when their choice to abandon a problem they failed to advance on or make a faster algorithm on, is unmasked from beneath the cloak of being "impossible" they covered it with, owing to their religion that P can not be NP.
instead of owning their choice to give up, they disguised the problem as impossible. when that disguise is revealed, they face their choice and face the possibility their failure was not excused by its being impossible, and their belief in intellectual superiority is challenged, and they percieve it as condescension.
the core contradiction is that the origin of the insecurity they are protecting against is their own choice to surrender, yet they try to blame it on the revealing of that choice by pretending its condescension. so they want to fight the voice that says the problem can be worked on ( and pretend its making them insecure ), to preserve their own narrative that it can't, instead of fighting their self defeatest narrative which gave them cause for the insecurity in the first place.
its a common misattribution of responsibility to preserve a protective delusion:
"it is not my fault i didnt solve this, the problem is impossible"
"it's not the fault of my choice to give up that I feel insecure, it's their fault for unmasking that my giving up was a choice."
misattribution of responsibility is a common maladaptive ( non workable ) response substitute instead of choosing to try another approach and create some results.
it so important to think about the culture of defeat around this because the stakes of these opportunities are so high: efficient acheduling, and dispatching, and gene sequence matching.
and the culture of defeat is essentially inefficiently systmeically and structurally draining resources from working on this. its of a significance that the psychology of this becomes important.
science works when it embraces questioning, including self questioning, of its methods, including its structural, systemic and cultural methods.
these are after all the operations or support and infrastructure faculties which support the work of science.
the culture of defeat and fake excuse around P and NP, lets people off the hook, as an excuse to shutter advances on whole classes of problems, and excuses a lack of results in making more efficient algorithms to meet those opportunities.
it becomes indoctrinated, a dogma, that P can not be NP, and the true believers as we have seen are all the more fervent to compensate for the absence of proof of impossibility.
and this slows progress, which doesnt work.
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.
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.
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.
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 ?)
http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...
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.
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.
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.
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"
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).
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.
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...
it's condescending towards the majority intuition with no reasoning about the actual issue whatsoever?
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 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.
> 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.