Dynamic Tractable Reasoning by Holger Andreas

Author:Holger Andreas
Language: eng
Format: epub
ISBN: 9783030362331
Publisher: Springer International Publishing

A decision problem belongs to the class P if and only if there is a Turing machine that decides it in polynomial time, i.e., there is a constant c > 0 such that the computation takes at most n c steps, where n is the length of the input string. Analogously, a decision problem belongs to the class EXP if and only if there is a Turing machine M and a constant c ≥ 1 such that M decides the problem taking at most computation steps.

The explanation of the class NP is more intricate. This class is intended to capture those problems whose “solution” can be verified in polynomial time. What a solution of a decision problem is varies from problem to problem. For the problem of deciding whether a formula ϕ of propositional logic is satisfiable, a presumed solution has the form of a valuation of the propositional constants that occur in ϕ. Whether or not such a valuation satisfies ϕ can be decided in polynomial time. Hence, deciding whether a given formula of the propositional calculus is satisfiable is a problem in NP. An actual solution of a problem instance is also called a certificate of it. In essence, a certificate is some piece of information that allows one to verify membership of the input string in the language under consideration.

An alternative definition of NP rests on the notion of a nondeterministic Turing machine that is allowed to make nondeterministic choices. Such choices can be used to encode potential certificates that are verifiable or falsifiable in polynomial time. Hence, NP stands for decidable in nondeterministic polynomial time. No actual machine is nondeterministic in this sense, however.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.