|
In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is one of the most fundamental complexity classes. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable"; in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb. ==Definition== A language ''L'' is in P if and only if there exists a deterministic Turing machine ''M'', such that * ''M'' runs for polynomial time on all inputs * For all ''x'' in ''L'', ''M'' outputs 1 * For all ''x'' not in ''L'', ''M'' outputs 0 P can also be viewed as a uniform family of boolean circuits. A language ''L'' is in P if and only if there exists a polynomial-time uniform family of boolean circuits , such that * For all , takes ''n'' bits as input and outputs 1 bit * For all ''x'' in ''L'', * For all ''x'' not in ''L'', The circuit definition can be weakened to use only a logspace uniform family without changing the complexity class. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「P (complexity)」の詳細全文を読む スポンサード リンク
|