The Holy Grail of Computer Science

[Anonymous No.6760417]

>If the solution to a problem can be quickly verified by a computer, can the computer also solve that problem quickly?

What would happen if it were solved /sci/? Would the singularity occur?

[Anonymous No.6760423]

Let's say i solved the traveling salesman problem. Does this imply in P=NP?

I'm not OP.

[Anonymous No.6760444]

>>6760417
>>If the solution to a problem can be quickly verified by a computer, can the computer also solve that problem quickly?

Meaningless garbage. State your question intelligently or >>>/g/tfo

[Anonymous No.6760451]

P = NP

divide by P;

So we have, N = 1.

SOLVED.

[Anonymous No.6760452]

Why do you fucks keep making these troll threads? This is easier to solve than that stupid .99999 = 1 stuff.

P != NP whenever N != 1

That is literally it.

[Anonymous No.6760459]

>>6760417
>a problem can be quickly verified

NP problems are NOT known be verifiable quickly by a computer if the answer is in the negative.

NP≟coNP is still an open question even if P≠NP≠AP

[Anonymous No.6760468]

>>6760423
>Does this imply in P=NP?
No.
And your mom solves the traveling salesman problem in polynomial time every night when she visits every state to find a large enough condom for me.

[Anonymous No.6760475]

>>6760423
It was solved within the past year.

Sorry mate, you were too late, so please don't hate, you can use your tears to masturbate

[Anonymous No.6760482]

>>6760452
I do not think you know what OP was asking.

[Anonymous No.6760544]

>>6760451
CS retards get BTFO

[Anonymous No.6760565]

kekd

Ill prove the fucking collatz conjecture and then ill show you faggots that P == NP along with proving the twin prime conjecture

either that or ill die trying

mfw RSA my ass

[Anonymous No.6760903]

>>6760482
i think hes trelling you

[Anonymous No.6760906]

>>6760565
http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf

[Anonymous No.6761235]

>>6760906
Did you even bother reading the shit you linked?

[Anonymous No.6761269]

It's a question mostly of theoretical interest. A polynomial-time algorithm is only guaranteed to be "efficient" in a purely mathematical sense. Suppose we found a polynomial time algorithm for solving TSP but it ran in O(n^94982389340892938690823689023869082309869038092389068908326) and had huge constant factors. That's a polynomial time algorithm but the naive O(n!) algorithm would be faster on all realistically solvable inputs, and even then, you'd just be better off using approximation algorithms.

[Anonymous No.6761280]

>>6761235
Why would anyone actually read what they post if someone else will point out what's wrong with it?

[Anonymous No.6761301]

>>6761269
With a large enough set that polynomial algorithm will run faster than the other one!

[Anonymous No.6761333]

>>6761301
literally just got a penis thinking about that

[Anonymous No.6761350]

How does p=/=np effect RSA? Isn't guessing a password the equivalent of the lottery? Randomly guessing at something you no information for. With np-complete problems you have a problem which you have to solve, with passwords you have no problem, you just have an input field and you have to guess the input.

[Anonymous No.6761896]

fuckin nerds

[Anonymous No.6761921]

>>6761350
You can sniff the code which is effectively:
define:
C = password in numbers (so a would be 1, b would be 2...)
P1= extremely large prime which is public
P2 = another extremely large prime which is hidden

They tell you P1 and your computer sends x=mod(C^P1,P1) to them. And they take this and do mod(x^P2,P2) which equals C.

if P=NP, then there is a function in polynomial time that can extract C from P1 without knowing the unlocking key P2. Current brute force just tries every single combination (which is in exponential time).

[Anonymous No.6761924]

>>6760906
Doublekek

>Implying I dont already know that paper

[Anonymous No.6762067]

>>6760417
problem - increase n by 1000000000000000
found solution - add 1 to n 1000000000000000 times

no/depending on the algorithm you use