NP-complete
I'm reviewing some stuff about P=NP problems and I'd like to discuss this subject, the halting problem and Cook's theorem. Also the Church-Turing hypothesis and the dissipation problem (a bit costs k(ln(2)) to copy or erase thermodynamically, so that the size of a bit is the thermodynamic efficiency scale).
A textbook I have talks about nd-choice; which is meant to decide if an input is acceptable. The choice amounts to guessing how to select inputs which is fundamentally reducible to selecting from 2 inputs. IOW we can only make guesses that a solution exists and a nondeterministic algorithm will succeed. NP means nondeterministic in polynomial time.
So we can't decide a priori that a problem can be solved unless we find an algorithm "in P" which we're sure will run and find a solution, for a restricted set of inputs. We can't say that a given solution will be found (the algorithm will halt) for all inputs, we can only constrain such solutions (for example, by having the algorithm reject inputs 'outside of' the domain allowed for P).
How otherwise is nondeterminism defined or, how do we know a problem is P or NP?
A textbook I have talks about nd-choice; which is meant to decide if an input is acceptable. The choice amounts to guessing how to select inputs which is fundamentally reducible to selecting from 2 inputs. IOW we can only make guesses that a solution exists and a nondeterministic algorithm will succeed. NP means nondeterministic in polynomial time.
So we can't decide a priori that a problem can be solved unless we find an algorithm "in P" which we're sure will run and find a solution, for a restricted set of inputs. We can't say that a given solution will be found (the algorithm will halt) for all inputs, we can only constrain such solutions (for example, by having the algorithm reject inputs 'outside of' the domain allowed for P).
How otherwise is nondeterminism defined or, how do we know a problem is P or NP?
0