PTIME class

Creator

Creator

Seonglae Cho

Created

Created

2023 Sep 9 16:34

Editor

Editor

Seonglae Cho

Edited

Edited

2023 Dec 19 4:38

Refs

Refs

deterministic polynomial time

A set of decision problems that can be solved by a deterministic

Turing Machine in a polynomial time

notion image

notion image

Tape

We can simulate steps of a

RAM-machine with a 3-tape TN in

Cubic complexity steps. Vice-versa in steps.

notion image

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.

P (complexity)

https://en.wikipedia.org/wiki/P_(complexity)

Backlinks

Circuit Complexity Turing Machine structure

Recommendations

//////