|
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
|
|
|
|
| # ¿ May 14, 2024 01:00 |
|
|
it's actually P=NIS
|
|
#
¿
May 14, 2017 23:52
|
|
|
carry on then posted:it's actually P=NIS we produce a proof of this statement *unzips*
|
|
#
¿
May 15, 2017 18:36
|
|
|
Doom Mathematic posted:I have a truly marvelous proof of this, which this margin is too narrow to contain.
|
|
#
¿
May 16, 2017 01:12
|
|
|
cis autodrag posted:my experience with algos class was that id feel like i was drowning in incomprehensible math for two weeks at a time and then suddenly something would click, then we'd move onto the next topic and it started all over again. algos class seems like one that really benefits from being taught by someone who is skilled at teaching, not just algorithms. mine was more of an infodump (with CLRS as the text lmao) and i feel like i'll have to do a bunch of self study the next time im out interviewing because i never really got it 
|
|
#
¿
Jun 8, 2017 15:57
|
|