|
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
|
#
¿
May 15, 2017 03:11
|
|
|
|
| # ¿ May 14, 2024 13:11 |
|
|
yeah but how do you know the answer is no? if it's so obvious, why can't anyone manage to prove it?
|
|
#
¿
May 15, 2017 03:30
|
|
|
the non-determinism stuff is a red herring, nobody thinks about non-deterministic computers except some theorists a few decades ago (note that the quantum computers you hear about in the news sometimes would not be able to solve NP-complete problems in polynomial time). but they were the first people to think about it, so they got to define and name the complexity class NP. the reason i like the checking explanation i gave before is that's how the inefficient algorithm actually works. for almost any problem that a normal person will encounter, the inefficient algorithm of "enumerate all possible solutions and check them until the right answer is found" will solve the problem. all problems in P are also in NP for this reason. but for those problems in P, we were able to come up with a better algorithm than the brute force enumeration, which is efficient for large input sizes. so what about the rest of the problems in NP that we haven't been able to do this for? are we just not smart enough, or is it really the case that we fundamentally can't do it? why would that be, what is it about these problems that makes them so different from the ones in P?
|
|
#
¿
May 15, 2017 03:40
|
|
|
people "knew" that fermat's last theorem was true because it's a simple calculation that you can test for many numbers to see a pattern. if you run a program to do that for a long time and see that it's always true, you have pretty strong evidence to believe the conjecture. that's not a general proof, because really big numbers can and do change the result unexpectedly. but even if you're satisfied with the unproven belief, you don't really know why it's true, you just found a pattern and declared it a law, you haven't really understood the nature of the universe any better. the ultimate proof of fermat's last theorem linked different fields of math together in previously unseen ways, and those discoveries will have far more lasting value to mathematics than simply a definitive answer to fermat's conjecture P vs. NP is a question about classes of problems, there's no way of just running it a bunch of times and convincing yourself that it's true. all you can do is look at the body of research work and conclude that because no one has been able to solve these problems efficiently, they must be fundamentally hard. but no one was able to solve relativity before einstein, so what if we just need the computing version of einstein to come along and revolutionize everything? don't you want to be that guy? it seems like we're gonna need him anyway even to prove that P != NP, because no one has the slightest idea of how to do that, which doesn't exactly inspire confidence in our current understanding of the hardness of these problems, does it?
|
|
#
¿
May 15, 2017 03:51
|
|
|
that is not the case. while computer touchers love to use the excuse of NP-completeness to explain why they can't solve a problem efficiently, the benefit to their employers of proving the inverse would be incalculably massive, since it would inherently include an efficient solution to all NP-complete problems! a company or government with this ability would absolutely devastate all competitors, like a grenade launcher at a knife fight
|
|
#
¿
May 15, 2017 03:59
|
|
|
most major industrial advances involve destroying whole industries full of jobs, and all the money getting redirected to the few companies involved in the advance, which become dominant players in the new industry. it's like the ultimate success story that could happen to a business, and there's no way they are gonna forego the opportunity just so some people get to keep their obsolete jobs. so why is this any different in the computer touching industry? it's not like the bosses want to pay us a deece figgy
|
|
#
¿
May 15, 2017 04:16
|
|
|
this concludes my stymie engagement, thank you for posting, try again next time
|
|
#
¿
May 15, 2017 04:21
|
|
|
if you want to understand the current state of the P vs. NP problem, and you don't already have a phd in cs with a specialization in computational complexity theory, you should read this: http://www.scottaaronson.com/papers/pnp.pdf
|
|
#
¿
May 15, 2017 04:37
|
|
|
Symbolic Butt posted:what I mean is that even if P = NP, the problems that we currently know as NP-complete will probably still be intractable. for more expansion on this, see Russell Impagliazzo's work, starting with the "five possible worlds"
|
|
#
¿
May 15, 2017 04:42
|
|
|
Doom Mathematic posted:I have a truly marvelous proof of this, which this margin is too narrow to contain.
|
|
#
¿
May 16, 2017 22:09
|
|
|
|
| # ¿ May 14, 2024 13:11 |
|
|
"i guess i'll try to make a new algorithm for [any mathematical problem that has a wikipedia page]" is phd level stuff
|
|
#
¿
Jun 7, 2017 23:19
|
|