|
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined〔J. Gill, "Computational complexity of probabilistic Turing machines." ''SIAM Journal on Computing'', 6 (4), pp. 675–695, 1977.〕 by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than or equal to 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial-time algorithm a sufficient (but bounded) number of times. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name ''Majority-P''.〔Lance Fortnow. Computational Complexity: Wednesday, September 4, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html〕 ==Definition== A language ''L'' is in PP if and only if there exists a probabilistic Turing machine ''M'', such that * ''M'' runs for polynomial time on all inputs * For all ''x'' in ''L'', ''M'' outputs 1 with probability strictly greater than 1/2 * For all ''x'' not in ''L'', ''M'' outputs 1 with probability less than or equal to 1/2. Alternatively, PP can be defined using only deterministic Turing machines. A language ''L'' is in PP if and only if there exists a polynomial ''p'' and deterministic Turing machine ''M'', such that * ''M'' runs for polynomial time on all inputs * For all ''x'' in ''L'', the fraction of strings ''y'' of length ''p''(|''x''|) which satisfy ''M(x,y)'' = 1 is strictly greater than 1/2 * For all ''x'' not in ''L'', the fraction of strings ''y'' of length ''p''(|''x''|) which satisfy ''M(x,y)'' = 1 is less than or equal to 1/2. In both definitions, "less than or equal" can be changed to "less than" (see below), and the threshold 1/2 can be replaced by any fixed rational number in (0,1), without changing the class. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PP (complexity)」の詳細全文を読む スポンサード リンク
|