|
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
|
|
|
|
| # ? Apr 29, 2024 04:25 |
|
|
let me ask you a question op, does N = 1?
|
|
#
?
May 14, 2017 16:41
|
|
|
there's been a lot of discoveries that moved stuff close to P than they used to be. we think we know everything mathematically, but we're pretty drat far away
|
|
#
?
May 14, 2017 19:10
|
|
|
we are imbeciles
|
|
#
?
May 14, 2017 19:17
|
|
|
i don't actually know what P/NP/NP-hard/NP-complete are and every time i try reading the wiki article my eyes glaze over
|
|
#
?
May 14, 2017 19:21
|
|
|
knuth said p probably does equal np and it's just gonna take forever to figure out how he said that half a forever ago so were on our way
|
|
#
?
May 14, 2017 19:46
|
|
|
Sweevo posted:i don't actually know what P/NP/NP-hard/NP-complete are and every time i try reading the wiki article my eyes glaze over hella oversimplifying: there are certain classes of problem where no matter how big the numbers are u could solve any of them with a deterministic computer (well, turing machine) in polynomial time (i. e. in this lifetime). these are P. a deterministic computer goes down each possible branch one at a time when multiple are possible there's another class which is a superset of the first, where no matter how big the numbers are, u could solve any of them with a non-deterministic turing machine, which considers all possible branches at the same time, which is a theoretical construct and can't exist, in polynomial time. these problems are NP problems now, if there is a problem A that every other problem in NP can be reduced to in polynomial time, A is NP-hard. it is at least as hard as any problem in NP but it doesn't necessarily belong to NP. if A is itself in NP, then A is NP-complete because every NP-complete problem must be NP-hard, every NP problem must be reducible to every NP-complete problem in polynomial time. so if we find a way to solve even a single NP-complete problem in polynomial time on a deterministic turing machine (the one that can exist in real life), we already have the means to convert every NP problem into that problem and solve them. it's hella unlikely that one of those problems exists, but because it seems like it's so close, there's a ton of activity around it. this is probably wrong and someone can school me but it's what i got out of my automata theory class 5 years ago
|
|
#
?
May 14, 2017 20:17
|
|
|
just think of problems that need to be guessed and checked until the solution is found vs ones we know the operation it takes to solve it right away
|
|
#
?
May 14, 2017 21:30
|
|
|
O(log N) = O(log NP) ? discuss
|
|
#
?
May 14, 2017 21:46
|
|
|
it's actually P=NIS
|
|
#
?
May 14, 2017 23:52
|
|
|
there was an engineer at hp a few years ago who produced a proof that p=np but it was quickly hushed up because it basically would have destroyed the computer touching industry
|
|
#
?
May 15, 2017 01:43
|
|
|
Stymie posted:there was an engineer at hp a few years ago who produced a proof that p=np but it was quickly hushed up because it basically would have destroyed the computer touching industry there's been like a thousand proofs that p=np, and there's always errors found in their work
|
|
#
?
May 15, 2017 01:45
|
|
|
LP0 ON FIRE posted:there's been like a thousand proofs that p=np, and there's always errors found in their work right 
|
|
#
?
May 15, 2017 01:46
|
|
|
it's in the cia headquarters vault, hanging out with the cold fusion reactor and the carburetor that gets 100mi/gal
|
|
#
?
May 15, 2017 02:10
|
|
|
math arent real
|
|
#
?
May 15, 2017 02:33
|
|
|
"you're fake math"
|
|
#
?
May 15, 2017 03:03
|
|
|
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
|
|
|
carry on then posted:there are certain classes of problem where no matter how big the numbers are u could solve any of them with a deterministic computer (well, turing machine) in polynomial time (i. e. in this lifetime). these are P. a deterministic computer goes down each possible branch one at a time when multiple are possible ok so basically 1) there are problems that can be solved in a reasonable time with a real computer 2) there are other problems that can only be solved in a reasonable time with a magic computer that can provably never exist 3) this question is asking if the the problems that can be solved only with a magic computer might also be solvable with a real computer using some special technique that's stupid. obviously the answer is no. like asking if you can travel faster than the speed of light. there, i saved you all a bunch of research dollars.
|
|
#
?
May 15, 2017 03:26
|
|
|
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
|
|
|
who cares people knew for 300 years that fermat's last theorem was probably true and then it was proven that yes, indeed it is true, and aside from one weird old british man getting his picture in the paper it didn't change the world in the slightest
|
|
#
?
May 15, 2017 03:36
|
|
|
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
|
|
|
JewKiller 3000 posted: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? they're harder, op yeeesh you guys are really overthinking this stuff
|
|
#
?
May 15, 2017 03:42
|
|
|
For hundreds of years people "knew" that geometry only needed four axioms, and the parallel postulate was a dodgy hack that was only needed because Euclid wasn't quite able to prove it. Then it turns out that whoops, actually you do need it. And the alternate geometries that you get when you replace the parallel postulate with something that's different and incompatible with it are actually pretty drat useful. That's the thing with unsolved questions - if you know what the answer probably is, then you tend to build up lots of other stuff based on that assumption of what the answer is. So if it turns out that you're wrong, that discovery is a massive game-changer.
|
|
#
?
May 15, 2017 03:46
|
|
|
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
|
|
|
plus there's little impetus to find an actual solution when an entire, massive sector of the economy is dependent on one particular assumption and potentially proving the inverse would ruin it entirely
Stymie fucked around with this message at 04:00 on May 15, 2017 |
|
#
?
May 15, 2017 03:55
|
|
|
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
|
|
|
that definitely sounds like the entire industry being destroyed to me the whole house of cards is dependent on a group of nerds pulling the wool over everyone's eyes by saying "it's really, super hard, trust us"
|
|
#
?
May 15, 2017 04:02
|
|
|
stymie's uncle once invented a carburetor that would get 1000 miles per gallon but the UAW dumped him in lake michigan
|
|
#
?
May 15, 2017 04:10
|
|
|
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
|
|
|
yes but since the industry is entirely a sham based off of mathematical chicanery and manipulation of public perception, actual definitive proof of the sham would bring it all crumbling down there's entrenched interests in ensuring the status quo, there's zero interest in doing anything actually worthwhile when there's billions to be made doing nothing at all
|
|
#
?
May 15, 2017 04:19
|
|
|
this concludes my stymie engagement, thank you for posting, try again next time
|
|
#
?
May 15, 2017 04:21
|
|
|
I remember reading that over the recent years a lot of researchers' opinions shifted to P = NP, but I think the majority of people still believe P != NP. Also I vaguely remember some kind of dual version of the problem that happened to be ButtP = ButtNP, even if it sounded unintuitive in the same way.
|
|
#
?
May 15, 2017 04:28
|
|
|
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
|
|
|
and you guys are being silly about crumbling down the industry. take testing for primality which was believed to not be in P for a long time. In 2003 they found a polynomial algorithm which was a neat theoretical result but that didn't mean poo poo in practice because the algorithm was still slow as poo poo. what I mean is that even if P = NP, the problems that we currently know as NP-complete will probably still be intractable.
|
|
#
?
May 15, 2017 04:38
|
|
|
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
|
|
|
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. 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?
|
|
#
?
May 15, 2017 05:58
|
|
|
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? tsp is kind of an awkward example because we don't know if it's NP. it's shown to be NP-hard which means it's at least as hard as NP-complete yes, I know, these definitions are convoluted Symbolic Butt fucked around with this message at 06:52 on May 15, 2017 |
|
#
?
May 15, 2017 06:46
|
|
|
a canonical easy to check hard to solve is any cryptographic hash
|
|
#
?
May 15, 2017 07:24
|
|
|
the traveling salesman equivalent would be what is the shortest input that gives the correct hash or, the other way around, traveling salesman is asking two questions: what's the shortest possible path, and what is one of those paths. checking that one of those paths is that length is easy but checking if it's the shortest possible is hard in the different kinda way I think
|
|
#
?
May 15, 2017 07:30
|
|
|
|
| # ? Apr 29, 2024 04:25 |
|
|
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. Thank you JewKiller 3000 for this succinct explanation
|
|
#
?
May 15, 2017 12:01
|
|