Complexity Classes
- Decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.
- Decision procedure is an algorithm that, given a decision problem, terminates with a correct yes/no answer.
- P Class : The class of polynomially solvable problems, P contains all sets in which membership may be decided by an algorithm whose running time is bounded by a polynomial.Problems to these solutions are easy to find.
- NP Class : (Non-Deterministic polynomial time).The class of non-deterministic polynomially acceptable problems, NP, contains all sets in which membership can be verified in polynomial time.Problems whose solutions are hard to find,easy to verify.
Related Posts
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment