deterministic polynomial timeA set of decision problems that can be solved by a deterministic Turing Machine in a polynomial time TapeWe can simulate steps of a RAM-machine with a 3-tape TN in Cubic complexity steps. Vice-versa in steps. P (complexity)In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.https://en.wikipedia.org/wiki/P_(complexity)
Alan Jo
