Why you anyone think P=NP

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > Why you anyone think P=NP

Berious: Nov 13, 2005

You'd have to be some sort of retard to even entertain the idea I mean seriously.

Yes I have just discovered this and I'm mad about it.

# ¿ May 14, 2017 16:29

Adbot: ADBOT LOVES YOU

# ¿ May 14, 2024 01:47

Berious: Nov 13, 2005

JewKiller 3000 posted:

you can ignore the mystical non-determinism stuff and think about it like this. a problem in P can be solved in polynomial time. a problem in NP can be checked in polynomial time, i.e. if i give you an already computed answer, you can check in polynomial time whether this answer is in fact correct.

so why does anyone think these classes are related? well basically computing is a young field so there was a ton of low hanging fruit, problems that seemed hard were solvable efficiently (in P) with simple strategies like greedy algorithms and memoization. for example dijkstra's shortest path algorithm, it's like the most obvious approach, an undergrad can prove it correct... you too could have an algorithm named after you if you had the foresight to be a computer science professor in the 1960s!

but there were still some problems where no known technique worked better in general than the brute-force strategy of enumerating all possible answers and checking each one. at first these problems were discovered independently, but researchers came to realize that they were all hard in the same fundamental way, and that any general polynomial time solution to one of them would work for all of them, so all of NP would be in P. that's what the NP-complete stuff is about

so there's a bunch of problems that a bunch of different smart people all thought they could solve efficiently, but none of them could do it, so it seems obvious that P != NP right? except nobody has been able to prove it, and they don't even really know how to go about attempting to prove it. math is hard

Thank you JewKiller 3000 for this succinct explanation

# ¿ May 15, 2017 12:01

Berious: Nov 13, 2005

cool av posted:

sure I could google this but for the sake of discussion... if i'm given a solution to say the traveling salesman problem, how do I check that it's correct (optimal) in polynomial time? is it one of those things where you have some known NP problem that's easy to check and you translate your other NP problem into that one first in order to check it?

Here is how I understand it:

P and NP are used to describe decision problems so you call it dTSP then ask "Is there a route under X?"

Then your magic box does it's working to find a route and tells you yes or no < this is the complicated bit

Then to check whether the box was full of poo poo you check it's working out by adding up the route yourself and decide whether it is under X < adding up is easy so it's P

Berious fucked around with this message at 12:13 on May 15, 2017

# ¿ May 15, 2017 12:10

Berious: Nov 13, 2005

Endless Mike posted:

is p = np good or bad for bitcoin

it would be great for buttcoin because all encryption would be worthless so someone could steal your real dollars as easily as your internet funbux

# ¿ May 15, 2017 17:21

Berious: Nov 13, 2005

Tiny Bug Child posted:

i have no idea how anyone could think P = NP tbh

my theory is they are bit fat retards who like anime

# ¿ May 15, 2017 21:37

Berious: Nov 13, 2005

indigi posted:

wow, they've been trying for decades? that's, like, forever for something as smart as a human being.

thing is it's such a ridiculous idea. just because you can check an answer for a thing easily doesn't mean there must be some as yet undiscovered special trick to make working out the thing easy too

# ¿ May 16, 2017 14:24

Adbot: ADBOT LOVES YOU

# ¿ May 14, 2024 01:47

Berious: Nov 13, 2005

if this is what mathematicians spend their time on then IMO they should quit their jobs and become NEET because at least then they would know all about something real like Naruto

# ¿ May 16, 2017 14:31

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > Why you anyone think P=NP