[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 130 KB, 707x883, email_pnp.jpg [View same] [iqdb] [saucenao] [google]
1564878 No.1564878 [Reply] [Original]

Just got an email: a lead researcher at HP Labs is presenting a proof that P != NP.

It's fairly long (100 pages), so you should probably set aside some time to read it.

Thoughts?

http://www.filesonic.com/file/16344911/pnp12pt.pdf

>> No.1564886

Well shit. Time to put on my reading glasses.

>> No.1564899

Fuck.

I wanted those million dollars...

>> No.1564904

If this is true, then too bad for the guy who discovered it and was basing his thesis off it.

>> No.1564924

>>1564904
That's what students are for, stupid.

>> No.1564937

I only know the basics of this problem, but can someone go over it?

Something about polynomial time

>> No.1564945

>>1564937
P denotes the subset of problems that have been proven to be solvable in polynomial time

NP denotes the all problems that have not been proven to be solvable in polynomial time

>> No.1564946

Is it legit? Downloading to find out, will read.

>> No.1564958

>>1564945
>In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"? The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice.

>> No.1564962

>>1564946
looks legit, I have no idea if the proof is valid though.

>> No.1564965

>>1564946

So, seems legit. Reading (will take a while). Fucking awesome if it's valid.

>> No.1564967

>>1564937
Wikipedia's example is also enlightening.
>Consider the subset sum problem, an example of a problem which is easy to verify but whose answer is suspected to be theoretically difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero", can be quickly verified with three additions. However, finding such a subset in the first place could take more time. The information needed to verify a positive answer is also called a certificate. Given the right certificates, "yes" answers to our problem can be verified in polynomial time, so this problem is in NP.

>An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

>> No.1564972

>>1564958
>>1564945
Thanks. Is this related to finding the shortest connecting route through a random cloud of points?

>> No.1564978

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

>> No.1564979

>>1564972
The shortest path problem is solvable in polynomial time, I believe.

The longest path problem, however, is still in NP.

>> No.1564983

>>1564962

Hivemind.

>> No.1564985

OP here. I should also note that Stephen Cook (formulator of the P/NP problem) says that this is "a relatively serious claim to have solved P vs NP."

>> No.1564988

What would this mean for the future of computation?

>> No.1564994

>>1564985
For sure.
I'd be willing to bet that a proof to any of the millennium problems would be serious.

>> No.1565002

>>1564994
And by serious, you mean, serious enough to give the prover $1,000,000.00.

>> No.1565003

all I understood was it has something to do with statistic? k-SAT LFP WTF FFFFFFFF

>> No.1565006

>>1564979
Traveling salesman problem is NP

>> No.1565013

>>1565003
I was surprised statistics was a route he took. Though I honestly thought P!=NP? was true but undecidable.

>> No.1565022

>>1564988
Probably not much. Most assumed P != NP, if however it was proven that P=NP, then that would be exciting.

Still cool to have a proof, if it is valid.

>> No.1565034

>>1564967
>>1564958

If you wouldn't mind explaining further, what exactly is the definition of "quickly"? Is it merely relative to the problem itself (I.E if the answer to X can be verfied in a certain amount of time, can the answer also be computed in a similiar amount of time?), was it the Polynomial Time you mentioned, or something else entirely?

>> No.1565050

>>1565034
Quickly in this case means polynomial time.
http://en.wikipedia.org/wiki/Polynomial_time#Polynomial_time

>> No.1565054

>>1565034
Quickly means that the time needed to solve in instance X of the problem is bounded by a polynomial function that takes the length of X as an input.

For example in the Subset Sum problem, there are on the order of 2^X combinations of numbers, and if Deolalikar's proof holds, you basically have to try them all.

>> No.1565064

>>1565034
If P=NP a computer could predict it's own output.

>> No.1565065

>>1565034
Look up Big O notation

>> No.1565071

so as far as what I understand from what I read on wiki and P NP for dummies, if proven, P != NP is a rather inconvenient truth for us isn't it (i.e. some problem takes shit load of time to solve and we have to deal with it)?

>> No.1565077
File: 40 KB, 577x285, pnp.png [View same] [iqdb] [saucenao] [google]
1565077

perhaps everyone was being close-minded, but I've read and been told by professors that this result is independent of our current formal logic systems and the math just isn't powerful enough yet for such a proof to be possible. I couldn't provide details, but has anyone else heard something similar about the intractability of this problem?

>> No.1565084

>>1565064
>If P=NP a computer could predict it's own output.

Is this what Deolalikar is saying (can't D/L the paper now)? Because predicting one's own output is proven impossible by Rice's theorem.

>> No.1565095

>>1565084
Including proving rices theorem wrong, If P=NP it would go all the way back to resolving Russell's paradox.

>> No.1565097
File: 10 KB, 235x214, images.jpg [View same] [iqdb] [saucenao] [google]
1565097

i can prove it in 2 seconds. N =1 YOU GODDAMN DUMBFAGS.

>> No.1565098

>>1565071
Well partially, but encryption is suppose to be computationally infeasible.

>> No.1565101

This totally proves there is no god.

>> No.1565107

>>1565095
If you have the PDF, can you offer us another spot for downloading? The Filesonic server seems to be severely overloaded ATM.

>> No.1565110
File: 6 KB, 175x182, 1281245789963.jpg [View same] [iqdb] [saucenao] [google]
1565110

>>1565097

or P = 0...

>> No.1565114

>>1565107
I'm not OP, go fuck yourself.

>> No.1565121 [DELETED] 

http://www.mediafire.com/?t8jzh33qw83dbvg

>> No.1565130

>>1565107
http://www.mediafire.com/?t8jzh33qw83dbvg

>> No.1565137

>>1565130
Thanks man.

>> No.1565154

I wish I knew enough about complexity theory to follow this. It's an incredible breakthrough if correct.

>> No.1565180

>>1565154
Same. I feel like I'm looking at the Mona Lisa but all I can see is a drawing of a woman with an indifferent face.

>> No.1565188

I read up a bit on Deolalikar, and he doesn't seem like someone talking shit. He has published work in peer-reviewed magazines, mostly results about the difficulty of showing that P = NP.

That doesn't mean he's infallible, but I can see how he got Cook's attention.

>> No.1565257

I can't believe /sci/ is eschewing this thread for religion, astrology and Richard Dawkins. It's pretty depressing.

>> No.1565267

>>1565257
Well no shit, 90% of /sci/ are trolls and underage that only has high school science class as their background and the only like 1 % of the remaining 10% understands wtf is written on there, I don't get it either.

>> No.1565282

>>1565257
It's too early for overt enthusiasm. Like with any math problem that offers great money and even greater prestige, attempted proofs come in by the dozens.
Even guys like Cook will need a few weeks to examine these 80+ pages of ideas from many different fields of math. They will not announce a "breakthrough" until they are sure they're not giving undue credit to some rube.

>> No.1565292

>>1565095

What does Russell's Paradox have anything to do with P=NP? That can be derived from naive set theory, which AFAIK has absolutely nothing to do with computational complexity.

>> No.1565298

>>1565282
There are a lot of different thigns rolling around in this paper.
I have a sinking suspicion that at least one is used improperly for the proof.
Regardless of if it is right it will take a while to verify it simply because of the breadth of the topic.

>> No.1565315

Damn it, it was my goal in life to be the first to prove this.

I hope it's wrong.

>> No.1565321

>>1565298
>>1565315
I think that there's a good chance of an error somewhere, however, even wrong it could outline a path to a correct proof. Wiles' first proof of Fermat's last theorem was wrong but only took about a year to fix.

>> No.1565336

>>1565321
Wiles' original proof had a hideous error, though, that required a lot of reworking. He said later that more than once he thought of giving it up as hopeless (though never for long).

>> No.1565347
File: 5 KB, 198x198, 1277933291198.jpg [View same] [iqdb] [saucenao] [google]
1565347

SPOILER

The story ends like this:
>Then, the relation computed by the least fixed point of J contains all the
individual least fixed points computed by the simultaneous induction as its sections.

>> No.1565358

I'm immediately suspicious by the use of random k-SAT as a basis for this. Information theory boundary proof are notoriously difficult. It's a neat proof concept, though... the proof takes a generalized P algorithm and figures out which problems it can solve, then shows that there exist NP problems which are not in that class. Looks promising, to say the least.

>> No.1565421

>>1565358
> From here, we obtain results that asymptotically almost surely upper bound the size of the largest cliques in the neighborhood systems on the Gaifman graphs that we study later.
> These provide us with bounds on the largest irreducible interactions between variables during the various stages of an LFP computation.

This looks like the hardest part. The Markov chain part is intuitive, if you think of it in terms of a travelling salesman on the Cartesian plane: the shortest path in such a graph can't have two links that cross each other. Of course, the math here improves upon these conditions.

The reduction to first order logic makes things from there on easy to understand. The author characterizes those problems that can be solved by FO(LFP). Then he says, if you can show that there exists a problem where the local conditions for any given locality are sufficiently messy (the "sufficient" part is the hard part), then that problem can't be solved in poly time.

Think of a set of cities you want to travel between. If there are several distinct clusters of cities, then you can say, "go from cluster A to cluster B to cluster C," and optimize within those clusters. That's easy. But if all the cities have similar spacing, the problem is much harder. And he's using a statistical method to show that for any proposed poly time algorithm, at least one such spacing will screw it up.

So, possible faults are in the statistical method, the results on PSPACE and P, or the generation of solutions.

>> No.1566110

bump for a potentially interesting thread,

>> No.1566162

>>1564985
Sauce? I can't find any quote like that from Cook.

>> No.1566215

A legit math/science thread? On my /sci/?

Unpossible!

>> No.1566219

It would be ironic if verifying this proof turned out to be just as hard as producing it.

>> No.1566227

I lol'd

>> No.1566259

>>1566219
It can't be verified in polynomial time

>> No.1566266

OP, assuming it is you who received this and are a researcher at HP labs, how does a research position at the HP labs pay? Are they ever hiring more researchers?

>> No.1567474

>>1566162
Cook said that in response to receiving this email.

>>1566266
I am not a researcher at HP Labs. Vinay sent the email to a small number of people (15-20), including Stephen Cook. Stephen then forwarded the email to the Theory Group @ UT (http://www.cs.toronto.edu/theory/).). It was again forwarded to graduate students at Canadian universities (as far as I know).

I believe the paper is still circulating mostly amongst academic circles.

>> No.1567488

I hope it's correct

people are spending way too much time on stupid shit like these problems

>> No.1567511

>>1567488
This is possibly the most important open problem in mathematics.

>> No.1567548

>>1567511

according to whom?

>> No.1567596

>>1567548
Ask anyone in the field of mathematics or computing.

>> No.1567590

>>1567548
It's important enough to warrant a million dollar prize. These problems weren't just selected because they're difficult. There's a reason there's no prize for solving Goldbach's conjecture.

P = NP would have incredible consequences. For instance, it would mean RSA is reversible, and codebreaking algorithms could be produced. It would revolutionize computing in general.

>> No.1567591

>>1567511
even with reading all this I still can't see how it will affect our lives. As far as I got it's just a question about "how long does it take to solve a question."
Can't seem to wrap my head around it. Will we be able to anything that we couldn't do?

>> No.1567623

>>1567590
that's not because it's "important"

it's because it's fucking annoying and they want to get it it over with

>> No.1567627

>>1567590
sooo.... this is gonna sound really dumb:
Why can't they just write the algorithms? Just assume there's no problem and start designing.
Why do they have to wait for some proof?

>> No.1567630

>>1567623
>There's a reason there's no prize for solving Goldbach's conjecture.

>> No.1567639

>>1567627
Because we don't know that such an algorithm exists yet, much less how to construct it. But if we get such a proof, suddenly a problem that would have taken a million years to compute on current technology can be reduced to days worth of processing.

>> No.1567647

Hahaha my college algorithms teacher was an idiot. He was so sure that a P=NP proof would come around eventually.

Good thing I slept all through that class.

>> No.1567650

>>1567639
Which is not to say that all problems can be reduced though. Some problems are more intractable than others

>> No.1567664

>>1567647
Well, we don't know for sure yet that Deolalikar's proof is correct. But I remember seeing a poll among researchers a year or two ago in which ~60% said they believe P != NP.

>> No.1567666

>>1567627
People have tried, turns out it's really hard, possibly impossible.

>> No.1567674

>>1567639
But how does this process look like?
Will some guy take the proof, make it into code and feed a problem into it?

>> No.1567683 [DELETED] 

>Actually Science and Math discussion on /sci/

You must be new here OP

>> No.1567681

"A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied "I can recognize great music but I can't create great music," the implication being that it's much harder to find a solution than to verify one. "

>> No.1567701

>>1567674
If we were to have a proof of P = NP, two things could happen:
The proof could be constructive, meaning there would be an explicit P-algorithm for solving an NP-hard problem. In this particular case, once we have a P-algorithm for solving one NP-hard problem, we can get such an algorithm for any NP-hard problem.

On the other hand, the proof could be nonconstructive, being a proof that it is possible to do it without giving an explicit way. This would incite a lot more research into discovering the actual algorithm, as the majority currently believes P != NP.

>> No.1567719

>>1567674
That depends on the form of the proof. If P=NP, odds are that the first form of the proof will be "here's an algorithm that solves a hard problem quickly, which is proof that one exists", in which case we're done - because we already know techniques to use such an algorithm to solve any possible supposedly hard problem. Alternatively, if the proof is just "according to all this mathematical magic, such an algorithm should exist, but I don't know why", we still have a long way to go (it's not that we wouldn't learn anything from it, but it will only get you a million dollars instead of billions if you actually find the algorithm itself).

>> No.1567740

>>1567701
(+1 knowledge)
Thank you very much for your answer! Didn't know about constructive/nonconstructive.

For anyone else wondering:
http://en.wikipedia.org/wiki/Constructive_proof

>> No.1568441

This is probably a stupid question but I'm really interested in knowing:
If correct, would this kill complexity theory?
Or would complexity theory thrive more than ever?

For example, finite group theory is almost dead because there are basically no stones left unturned in that field. I'm wondering how much research would be left to be done beyond this point.

>> No.1570304

>>1568441
bump for curiosity

>> No.1570380

Aw, fuck.
I'm entering a computer science bachelors program next month, I don't want another class added to my schedule.

>> No.1570437

>>1570380
They can't change your requirements after you enter. At least, that's how it is at my undergrad.

>> No.1570501

Well, if he's correct then there goes one more thing in this field that would let me be remembered as a contributor had I solved it.

I guess this just reminds me I'm destined to live and die unnoticed.

>> No.1570552

>>1570501
Aye. It's a curse.

>> No.1570799

>>1568441
Nope, there are many other complexity classes with practical relevance. There are probabilistic algorithms, approximative algorithms, and problems which take exponential time only for a few degenerate cases. The P<NP theorem would say nothing about the average difficulty of these problems.

>> No.1570818

>>1570799
Thank you.