Why is a brainlet CS question one of the Millennium Prize Problems?

>>8661408
ya I know right, go ahead and solve it then OP since all CS = brainlets

>>8661414

This. Once you realize you can't do it, go fuck yourself, OP.

>>8661408
P is NP

saying otherwise is believing that the nondeterminism fairy extends sets of languages using her magic powers

>>8661408
>Why is a brainlet CS question one of the Millennium Prize Problems?
An algorithm for solving NP problems in P time would mean that we could easily write a computer program to prove all true theorems.

It would mean that we could easily write a computer program to simulate the universe.

Basically, P=NP means that most science and math would be put out of business by computers.

It seems worthwhile to find out if P=NP or not.

>>8661408
FWIW, you could solve all the other Millennium prize problems using your solution if P=NP.

>>8661463
>An algorithm for solving NP problems in P time would mean that we could easily write a computer program to prove all true theorems.
>It would mean that we could easily write a computer program to simulate the universe.
>Basically, P=NP means that most science and math would be put out of business by computers.
>>8661466
>FWIW, you could solve all the other Millennium prize problems using your solution if P=NP.

And this is why CS majors are called brainlets. They don't even understand their own field.

>>8661463
>An algorithm for solving NP problems in P time would mean that we could easily write a computer program to prove all true theorems.

This is the what the average "superior intellect" on /sci/ truly ""knows"" about Computer Science.

>>8661463
>An algorithm for solving NP problems in P time would mean that we could easily write a computer program to prove all true theorems.

You're an idiot who's never heard of Godel.

>>8661473
>implying that wasn't a CS major

>>8661472
>And this is why CS majors are called brainlets. They don't even understand their own field.
>tfw too smart to explain what they mean

http://www.scottaaronson.com/papers/pnp.pdf
>Expanding on G¨odel’s observation, some modern commentators have explained the importance of P ?= NP as follows. It’s well-known that P ?= NP is one of the seven Clay Millennium Problems (alongside the Riemann Hypothesis, the Yang-Mills mass gap, etc.), for which a solution commands a million-dollar prize [75]. But even among those problems, P ?= NP has a special status. For if someone discovered that P = NP, and if moreover the algorithm was efficient in practice, that
person could solve not merely one Millennium Problem but all seven of them—for she’d simply
need to program her computer to search for formal proofs of the other six conjectures.1

>>8661479
>You're an idiot who's never heard of Godel.
Godel is actually the guy who came up with the idea of using a P=NP algorithm to search for all proofs. So no. I *have*. And no, his incompleteness theorem does not present the problem you think it does.

>If there actually were a machine with [running time] ∼ Kn (or even only with ∼ Kn2) [for some constant K independent of n], this would have consequences of the greatest magnitude. That is to say, it would clearly indicate that, despite the unsolvability of 4 the Entscheidungsproblem [Hilbert’s problem of giving a complete decision procedure for mathematical statements], the mental effort of the mathematician in the case of yesor-no questions could be completely [added in a footnote: apart from the postulation
of axioms] replaced by machines. One would indeed have to simply select an n so large that, if the machine yields no result, there would then also be no reason to think further
--Kurt Godel in a letter to John von Neumann.


about the problem.

>>8661491
>>If there actually were a machine with [running time] ∼ Kn (or even only with ∼ Kn2) [for some constant K independent of n], this would have consequences of the greatest magnitude. That is to say, it would clearly indicate that, despite the unsolvability of 4 the Entscheidungsproblem [Hilbert’s problem of giving a complete decision procedure for mathematical statements], the mental effort of the mathematician in the case of yesor-no questions could be completely [added in a footnote: apart from the postulation
>of axioms] replaced by machines. One would indeed have to simply select an n so large that, if the machine yields no result, there would then also be no reason to think further
>--Kurt Godel in a letter to John von Neumann.

>One would indeed have to simply select an n so large that, if the machine yields no result, there would then also be no reason to think further

Just because Godel was a great logician, doesn't mean everything he said was smart. Empiricism/"checking things" is not and never will be a valid proof method.

>>8661499
>Just because Godel was a great logician, doesn't mean everything he said was smart.
That's true. But I'm going to trust some of the smartest physicists and logicians over the opinion of an anonymous dunning-krugerand on 4chan.

>Empiricism/"checking things" is not and never will be a valid proof method.
That isn't what Godel was advocating.

>>8661509
>That isn't what Godel was advocating.
Reread your own quote

Solving P = NP will most likely not have any immediate consequences for any practical applications of computer science. The proof is unlikely to be a constructive one. Proving that you can reduce any program in NP to a program in P doesn't do you any good if you don't know how to actually do the conversion.

I swear, /sci/ is one of the least educated boards on computers on all of 4chan.

>find a P = NP algorithm running in Θ(n^99999999999) time
>nothing changes

>>8661516
>Reread your own quote
He's advocating exhaustive search with a theorem deriver. It isn't an empirical check like when you use a Bayesian method to spot check a theorem. If a proof is found it is exact and unambiguous.

>I swear, /sci/ is one of the least educated boards on computers on all of 4chan.
If you feel it necessary to add ad hominem to your point, that probably means your point isn't strong enough to stand on its own.
>Solving P = NP will most likely not have any immediate consequences for any practical applications of computer science
Only because almost everyone thinks P=/=NP.

>>8661482
>>8661491

"P =Tractable" is a fucking meme. Even if P=NP and we had an Θ(n^4) solution to SAT, we still wouldn't be able to crack RSA.

>>>/g/o back to >>>/g/

>>8661535
I cited a 119 page paper by a top computer scientist & physicist that disagrees with you. If you're so smart, I suggest you read it and tell him why he's wrong. If you can prove it you could be publishing yourself instead of shitposting on 4chan.

>>8661463
>It would mean that we could easily write a computer program to simulate the universe.

Prove the universe is in NP.

>Basically, P=NP means that most science and math would be put out of business by computers.

Prove science and math are in NP.

>implying there are no complexity classes above NP

This is what brainlet CSers actually believe

Don't mind me. Just trying to solve:
P = BQP

>>8661542
>argumentum ad verecundiam

You should be able to do the simple math on your own. A n^4 algorithm for SAT composed with the usual n^3*log(n) Cook-Levin algorithm for converting NP problems into SAT gives a complexity of n^7log^4(n).

A typical 1024bit RSA key will take approximately (2^10)^7*log^4(2^10) = 2^70*10000 ~= 2^84 operations to crack. That will require 1.5*10^8 years on a single core 4GHz machine.

>>8661549
P = NP isn't even necessary to beat humans, who work on heuristics. It is completely irrelevant to the singulo AI meme

File: tmp_25741-images.duckduckgo.com741659238.gif (32KB, 380x228px) Image search: [Google]

32KB, 380x228px

>>8661482
>she

>>8661667
i had one programming book that always referred to the reader as a 'she' and it pissed me the HEK off

>>8661584
That's a lot of supposition to construct something that doesn't even qualify as a counterexample.

>>8661529
>If you feel it necessary to add ad hominem to your point, that probably means your point isn't strong enough to stand on its own.

Not him, and I'm nitpicking, but it doesn't necessarily mean that. It says more about how he probably feels about his point than it does the point itself.

>>8661727
Fair enough. It indicates he feels insecure about the quality of his point and is worried he may be incorrect.

>>8661408
CS on highest level is Math research.

>>8661667
This. Fuck everyone who does that.