|
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? 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
|
|
|
|
| # ? Apr 28, 2024 23:31 |
|
|
how is polynomial time defined? im guessing "in one lifetime" isn't an actual si unit.
|
|
#
?
May 15, 2017 12:20
|
|
|
gently caress the guy who solved Fermat's last btw two japanese mathematicians killed themselves when nobody took their work seriously, then another mathematician shows that if they were right it proves fermat so all of a sudden this stodgy douchebag comes riding into the scene to feed his ego
|
|
#
?
May 15, 2017 12:39
|
|
|
A Pinball Wizard posted:how is polynomial time defined? im guessing "in one lifetime" isn't an actual si unit. basically, you have some number n that represents how large the input to your problem is - for example, how many cities your travelling salesman is trying to visit if your algorithm runs in "polynomial time", that means that you can pick some finite number c so that it takes less than nc operations to complete, no matter what input you run it on note that this doesn't mean it runs "fast". there are lots of situations where people use brute-force exponential algorithms even though polynomial-time algorithms exist, because on all the inputs small enough to be feasibly solved the brute-force method is faster. Jabor fucked around with this message at 12:43 on May 15, 2017 |
|
#
?
May 15, 2017 12:41
|
|
|
this is a good post about tsp: https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en
|
|
#
?
May 15, 2017 13:08
|
|
|
based on barely understanding anything in this thread I'm gonna say that P obviously = NP
|
|
#
?
May 15, 2017 13:32
|
|
|
i dont know, op sorry
|
|
#
?
May 15, 2017 14:19
|
|
|
is p = np good or bad for bitcoin
|
|
#
?
May 15, 2017 14:25
|
|
|
pee = op
|
|
#
?
May 15, 2017 14:58
|
|
|
A Pinball Wizard posted:how is polynomial time defined? im guessing "in one lifetime" isn't an actual si unit. broadly it's the category of O(n^K) where k is basically just the number of nested loops your algorithm needs
|
|
#
?
May 15, 2017 15:57
|
|
|
brute forcing traveling salesman, on the other hand, is O(n!) aka get hosed
|
|
#
?
May 15, 2017 15:58
|
|
|
Anneal my simulated rear end.
|
|
#
?
May 15, 2017 17:04
|
|
|
Why would anyone not think P=NP and that we're just all loving idiots who dont know poo poo
|
|
#
?
May 15, 2017 17:12
|
|
|
my username dictates i must post in this thread.
|
|
#
?
May 15, 2017 17:20
|
|
|
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
|
|
|
Encryption relies on picking a big number. sorry thats underselling it. a REALLY big number. sure thats a system that will remain foolproof.
|
|
#
?
May 15, 2017 17:26
|
|
|
power botton posted:Encryption relies on picking a big number. sorry thats underselling it. a REALLY big number. lol
|
|
#
?
May 15, 2017 17:40
|
|
|
its the number of bitcoins in my cybersafe, peasant
|
|
#
?
May 15, 2017 17:53
|
|
|
JewKiller 3000 posted: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 looks cool, op btw i'm the ironic complexity theory
|
|
#
?
May 15, 2017 18:17
|
|
|
carry on then posted:it's actually P=NIS we produce a proof of this statement *unzips*
|
|
#
?
May 15, 2017 18:36
|
|
|
carry on then posted:we produce a proof of this statement *unzips* I have a truly marvelous proof of this, which this margin is too narrow to contain. 
|
|
#
?
May 15, 2017 20:41
|
|
|
Doom Mathematic posted:I have a truly marvelous proof of this, which this margin is too narrow to contain.
|
|
#
?
May 15, 2017 20:48
|
|
|
power botton posted:Why would anyone not think P=NP and that we're just all loving idiots who dont know poo poo b/c all you would have to do to prove it is find a polynomial time algorithm, no matter how slow or lovely, for any problem in NP, and lots of smart people have been trying to do that for decades while getting nowhere. also P != NP is the intuitive answer. i mean if you think about the problems involved it's pretty obvious there are no easy solutions for them. i have no idea how anyone could think P = NP tbh
|
|
#
?
May 15, 2017 20:59
|
|
|
Doom Mathematic posted:I have a truly marvelous proof of this, which this margin is too narrow to contain.
|
|
#
?
May 15, 2017 21:22
|
|
|
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
|
|
|
Doom Mathematic posted:I have a truly marvelous proof of this, which this margin is too narrow to contain.
|
|
#
?
May 16, 2017 01:12
|
|
|
Tiny Bug Child posted:b/c all you would have to do to prove it is find a polynomial time algorithm, no matter how slow or lovely, for any problem in NP, and lots of smart people have been trying to do that for decades while getting nowhere. also P != NP is the intuitive answer. i mean if you think about the problems involved it's pretty obvious there are no easy solutions for them. i have no idea how anyone could think P = NP tbh Yeah: proving theorems in a formal system is an NP problem, so P=NP is roughly equivalent to saying "maths is secretly easy". I recently found out that we already have an algorithm for some NP-complete problem that we can show runs in polynomial time iff P=NP, but no-one can prove anything about its worst-case asymptotic behaviour.
|
|
#
?
May 16, 2017 10:16
|
|
|
Tiny Bug Child posted:b/c all you would have to do to prove it is find a polynomial time algorithm, no matter how slow or lovely, for any problem in NP, and lots of smart people have been trying to do that for decades while getting nowhere. also P != NP is the intuitive answer. i mean if you think about the problems involved it's pretty obvious there are no easy solutions for them. i have no idea how anyone could think P = NP tbh wow, they've been trying for decades? that's, like, forever for something as smart as a human being.
|
|
#
?
May 16, 2017 11:44
|
|
|
P>NP
|
|
#
?
May 16, 2017 12:00
|
|
|
0.999999=1
|
|
#
?
May 16, 2017 12:00
|
|
|
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
|
|
|
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
|
|
|
donald trump thinks p is np
|
|
#
?
May 16, 2017 14:33
|
|
|
MALE SHOEGAZE posted:donald trump thinks p is np
|
|
#
?
May 16, 2017 14:44
|
|
|
Berious posted: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 you're taking "easy" too literally
|
|
#
?
May 16, 2017 14:49
|
|
|
MALE SHOEGAZE posted:donald trump thinks p is np 
|
|
#
?
May 16, 2017 18:55
|
|
|
Berious posted: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 s/mathematicians/computer touchers/
|
|
#
?
May 16, 2017 20:10
|
|
|
Doom Mathematic posted:I have a truly marvelous proof of this, which this margin is too narrow to contain.
|
|
#
?
May 16, 2017 22:09
|
|
|
WrenP-Complete posted:my username dictates i must post in this thread. P=NURTIS
|
|
#
?
May 20, 2017 22:13
|
|
|
|
| # ? Apr 28, 2024 23:31 |
|
|
P=ENIS
|
|
#
?
May 20, 2017 22:35
|
|
