PTIME
In complexity theory PTIME is the class of decision problems that can be solved on a deterministic Turing machine in polynomial time, i.e. the number of computation steps is bounded by a polynomial function, where the length of the input is the argument. The length of the input is the length of the appropriate coding, e.g. for numbers this coding is usually of logarithmic length with respect to the number itself (a number n can be coded using log n symbols).
PTIME is usually just named "P" and then forms part of one of the big open problems in mathematics: P =? NP (see Complexity classes P and NP). The problems in PTIME are often considered to be the problems that are effectively computable, since no problem in PTIME requires exponential time.
Referenced By
List of mathematical topics (P-R)
|
