Problem:
Is NP countable?
Short answer:
yes
Proof:
For each problem in NP - there exists a non-deterministic Turing machine as verifier.
As we can encode non-deterministic Turing machine as finite binary string, the set of non-deterministic Turing machine is countable, therefore the set NP is also countable.
Is NP countable?
Short answer:
yes
Proof:
For each problem in NP - there exists a non-deterministic Turing machine as verifier.
As we can encode non-deterministic Turing machine as finite binary string, the set of non-deterministic Turing machine is countable, therefore the set NP is also countable.
No comments :
Post a Comment