azuarc posted...
For whatever it's worth, I have a math degree with a computational focus that started off as a computer science major, and I've got NFC what the terms being bandied about are (just from reading over the paper.) Never heard of them. I've heard of p vs np, but not in the context of any of my coursework.
So yeah, screw you guys who are saying this is basic stuff that everyone who has even dabbled in the field should know. Or screw Penn State for sucking horribly. Probably both.
Math that uses computers is quite different from CS. In fact, this is the EXACT area where it is different from CS now that I think of it. Unless you are in graph theory (because it feels like EVERY interesting problem in graph theory is NP-complete or NP-hard), there's a good chance you may never deal with these sorts of things.
That said, if you took at least 2 years of CS I would expect you to know the following (in terms of complexity theory).
1) Basic runtime analysis on P. Selection sort is best, worst, and average case n^2 work. Merge sort is BC n (maybe n log n, depends on implementation), WC/AC n log n. Quick sort is BC/AC n log n, WC n^2, but still typically outperforms merge sort. (you may know a potential problem with a system is a "quicksort attack")
2) Undetermined areas. There exists a class of problems that we believe is "hard", but cannot prove. We call it NP-hard. Examples include: general boolean satisfiability, 3-satisfiability, graph coloring, Hamiltonian cycle, travelling salesman problem, subset sum. All known solutions take exponential time. Examples do NOT include 2-satisfiability. (in general, a more constrained problem may be able to be solved in reasonable time)
3) Definitely hard. You are vaguely aware there exists problems which are known to be harder than the problems in 2. You might not know any examples or names of complexity classes, but if you do, you probably know generalised chess, checkers, and go (with the superko rule) are EXPTIME-complete.
4) Impossible. There exist problems which cannot be solved by a computer, ever. The classic example is the halting problem (will the given program ever hang?).
Also, as I noted, the paper contains nothing of actual value to the public and is at best of marginal interest to those in the field, so yeah, only there for novelty.
--
assert(!hotterThan(foo, "Hot Nymphomaniacal Lesbian Mind-Controlling Dominatrix Fairy Doctors with glasses"))