|
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
|
|
|
|
| # ¿ May 14, 2024 02:19 |
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
if you want to work through some math: https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
|
|
#
¿
Jun 7, 2017 21:46
|
|
|
SpaceClown posted:If n is one or p is 0 p=np. Stupid comp sci idiots. this joke was already done. mods ban this chucklefuck
|
|
#
¿
Jun 9, 2017 15:38
|
|
|
OldAlias posted:cs texts are lol and a racket. unless the material and tests closely follow it find a bunch of other resources as supplement. our course used sedgewick which is worthless for a good portion of the class. he invents his own notation which no one uses because he has problems with Big O - but his problems are addressed with theta and omega, which i guess he never heard of. what was his notation like? I remember it was just kind of vague, less formal. "This algorithm is n log n", like that
|
|
#
¿
Jun 9, 2017 20:20
|
|
|
spankmeister posted:Did u know selection and insertion sort are actually the same? #wow #whoa the scratching sounds always bother me in these videos, gently caress. and those animations are a little bit too much but what matters: I guess that they're the "same" in the sense that insertion sort is just a better tweaked version of selection sort. maybe something to do with dynamic programming? I'm surprised that I never heard about this before but then again I didn't do a BS CS Symbolic Butt fucked around with this message at 01:52 on Jun 11, 2017 |
|
#
¿
Jun 10, 2017 23:47
|
|
|
|
| # ¿ May 14, 2024 02:19 |
|
|
Max Facetime posted:one such number is nextup(0.0) 1.401298464324817e-45 2.802596928649634e-45 
|
|
#
¿
Jun 12, 2017 10:58
|
|