#588 by Cito di Pense » Dec 24, 2021 5:35 am
There are lots of interesting problems in computation (e.g. involving paths on graphs) which we (so far) only know how to solve by brute-force methods, trying every alternative to see if it works, and this takes exponential or factorial time to compute because of the combinatorial how-many-ways aspect. A P problem can be solved in polynomial time, that is, N to some real number power where N is the size of the problem, and this is considered easy even if the power is a million, such as the number of nodes on a graph and the multiplicity of edges emanating at each node, even on average. Above, we have problems A and B and we want to know if they are equivalent in difficulty. A way it's sometimes expressed is that it's easier to check a solution than to find one. An NP algorithm solves in non-deterministic-polynomial time, for example, by guessing at solutions, and there's even educated guessing. NP is the class of questions where solutions can be verified in polynomial time when presented without much useful information about how the solution was achieved (by "guessing"). The wikipedia article is eminently readable, at least for the first few paragraphs.
The kind of question I posted up there is merely one of understanding the definitions, which have subtlety, including how a "decision problem" is defined. Apropos of this discussion here, by way of analogy, it's easier to check someone's proof than it is to come up with the proof. For me, it's about how we only learn mathematics by solving lots and lots of exercises, instead of just checking the solutions of "worked examples". When FW uses the word "proof", he has no idea what he's talking about. If FW is persuaded by an argument, or even by the turn of phrase in some google search result, he calls it a proof, but this isn't mathematics, and it certainly isn't proof. It's only where we run off the rails. It's a "Chalk Mark in a Rainstorm", to recall an image that Joni Mitchell used as an album title, and I'm glad its author is an artist I respect. It's ridiculous to treat the problem of "idealism, repeated" as more difficult than P vs. NP until FW shows that he has any kind of expertise at all. If he's Ransford, at least he has some nameable expertise, even if it's a few decades old. Ransford is a crank who stopped doing academic work decades ago, and who now self-publishes in gray literature and posts at ResearchGate.
Хлопнут без некролога. -- Серге́й Па́влович Королёв
Translation by Elbert Hubbard: Do not take life too seriously. You're not going to get out of it alive.