P (PTIME), EXPTIME, DTIME and simulation by Turing-equivalent machines in polynomial time

Introduction

Introduction

P (aka PTIME): Polynomial in time. \(O(poly(n))\)

EXPTIME: \(O(2^{poly(n)})\)

DTIME(f(n)) .ie P is DTIME(poly(n))