/sci/ - Science & Math

Read the proof sketch in the intro. Reading the rest now. Seem legit

this is the preliminary, and I'm not going to read the freaking thesis just to know why P!=NP. Can some one explain it in a few words?

A physicist and an engineer are in a hot-air balloon. They've been drifting for hours, and have no idea where they are. They see another person in a balloon, and call out to her: "Hey, where are we?" She replies, "You're in a balloon," and drifts off again. The engineer says to the physicist, "That person was obviously a mathematician." They physicist replies, "How do you know that?" "Because what she said was completely true, but utterly useless."

>>1571543
if it was that easy to sum it up in a few words, the proof would have been thought up years ago

I don't know what either P or NP is

MOTHERFUCKIN FIELDS MEDAL IN THIS SHIT

>>1571543
Basically if P = NP, then a result from statistical mechanics explodes the universe

Looks like he picked up some confidence and added the dedication page. Maybe he heard something from Cook's colleagues?

>>1571513
Thank you for the 549th thread about this.

somebody just explain in a few words what p versus np is all about

fuckin mathematicians... get to the point already

fucin' P VS NP

How does it work?

N=1

>>1571563
simple algorithms v difficult ones
are they the same?

P = NP: There are fucking pink unicorns and everyone who can follow a series of steps is Gauss

P != NP: The universe sucks as always... only we know a little more detail as to just how much it sucks.

>>1571563
P = a class of problems that can be solved in polynomial time using a (deterministic) turing machine
NP = a class of problems that can be solved in polynomial time using a nondeterninistic turing machine - dasically a machine that can calculate branching programs as fast as if they didn't branch.

P = NP

N = P/P

N = 1.

You're welcome Humanity.

>>1571563

coming form a dude taking as comp sci algorithms and complexity class...

P is the set of all problems solvable in polynomial time

NP is the set of all problems where if given a correct answer, you can verify it is a correct answer in polynomial time. They don't have to be solvable in poly time to be in NP.

There were problems in NP (called NP-Complete) that we didn't know how to solve in poly-time, but it was never definitively proven that they could or could not be solved in poly time. (i.e. coloring a graph with only 3 colors such that no edge has the same color at both ends is an NP-Complete problem)

If the proof holds, this means that those NP complete problems are definitely not solvable in poly time. Which sucks for computers because exponential running times are a bitch.

>>1571513
>P != NP
GOD FUCKING DAMMIT.

>>1571600
As a side to what he said, P and NP are more associated with computer science, rather than math. This actually means a shitload for the comp sci world.

So doesn't this guy get a million dollars for this proof?

>>1571633
If it's correct, yes.

>mfw P != NP

http://gregbaker.ca/blog/2010/08/07/p-n-np/

>>1571660

Same. :(

>>1571600
I may be wrong but knowing p != np doesn't tell us whether a specific problem has an easy solution, just that SOME problems do not. P = np would have been a far greater finding, as we would always know that there is a 'best' algorithm out there.

But I was more into bioinformatics.

GOD FUCKING DAMMIT AND I WAS HOPIND I'D SAVE SOME MONEY ON MY BUSINESS TRAVELS!

>>1571822
Here's the list of SOME problems. There are over 3000 known NP-complete problems.

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

>.pdf
sure is virus in here

>>1571875
>hp.com
sure is reputable in here.

>>1571875
>>1571884
sure is samefag in here

>>1571870
No, you misunderstand. What I am saying is that even knowing p != np, we cannot yet tell whether a problem actually has a fast solution that we haven't yet found, or whether a problem genuinely has no fast solution.

>>1571822
Since NP-complete problems can be reduced to each other, it basically tells us than none of the NPC problems have an easy solution.

Vinay Deolalikar
Education

Ph.D. (Electrical Engineering, jointly with Mathematics) University of Southern California, May 1999. Thesis: On splitting places of degree one in extensions of algebraic function fields, towers of function fields meeting asymptotic bounds, and basis constructions for algebraic-geometric codes)

Masters in Electrical Engineering (5-year) Indian Institute of Technology, Bombay, July 1994. Dissertation: New approaches to learning and classification in feedforward neural networks

>Electrical Engineering
>Engineering

No more gay tier, huh?

>>1571884
hpl.hp.com
>sure is clever in here

>>1571928
No, you. P != NP is EXACTLY the result that all of these problems genuinely have no fast (general, exact) solution.

What you probably mean ist that there still might be approximative or probabilistic algorithms that do well enough in practice, but don't solve the problem to the full extent.

>>1571945
hpl.hp.com
hp.com = root domain
hpl = subdomain
therefore: hpl is part of hp.com

>sure is dumbfuck in here.

If P =/= NP, cryptographers are happy
If P = NP, cryptographers are sad

>>1571960
sure is trolled in here

>>1571513
There have been at least 59 proofs asserting either P=NP or P!=NP in the last two decades. This one will likely be a failure as well.

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

>>1571968
>If P = NP, cryptographers are sad
Not really. There still exist problems firmly in P that take longer than the universe's age to solve given a large enough input.

>>1571986
>Not really. There still exist problems firmly in P that take longer than the universe's age to solve given a large enough input.

but then it would be just a matter of time, before enlarging key size to cope with computing power would become impractical, wouldn't it ?

bump for actual science

oh fuck /sci/
I made a thread about it some minutes ago and only got a couple of sages

>>1572244
>bump for actual science
>actual science
not on my /sci/ This thread needs more religion
derp

what if N = 1?

>>1572276
fucking lol'd