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?
Replies
You are reading an archived discussion.
Related Posts
Hi All,
As promised, CrazyBoy is back with Can You Design; series again.
This thread is the part II of the "Can you Design" series. All of us extensively use...
Hi guys ,
This is a thread where you should post what you people have learnt after joining CE.
Everyone mostly join for search of something they need and if...
hi. i'm lohit suri .i'm havin 73% agg. till 2nd yr. b .tech frm rtu.can u tell me the procedure for summer training in iits
I wanted to do the project on the networking basis. Will you please help in selecting the project for B.E. final year in the computer science.
😕
As a part of my final year project Im planning to shape a Fuzzy based Optical character Recognition system. For that purpose I plan to use a 16 or 8...