PTIME class

Creator

Creator

Created

Created

2023 Sep 9 16:34

Editor

Editor

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

t

steps of a

RAM-machine with a 3-tape TN in

O(t^3)

Cubic complexity steps. Vice-versa in

O(t)

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.

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

Recommendations

//////