TOC

DFA formally

NFA Formally

eNFA Formally

CFG

Chomsky Normal Form

Greibach Normal Form

PDA formally

PDA Transitions

One-tape TM

Multi-Tape to Single-Tape TM

NTM to DTM

The Class P (formally)

Informally, the set of all decision problems solvable in poly time by a deterministic machine

Verifiers

The Class NP

Alternatively: NP is the class of languages that can be decided by a non-deterministic TM in poly time

NTIME

EXPTIME

TIME

SPACE

NSPACE

Relating time and space complexity

If a TM runs in f(n) TIME, it uses at most f(n) SPACE

If a TM runs in f(n) SPACE, it uses at most 2^(f(n)) TIME

PSPACE

NPSPACE

Relationships between complexity classes

PSPACE = NPSACE (every f(n) space NTM has an equivalent f(n)² space DTM)

P subset PSPACE (If a TM runs in f(n) TIME, it uses at most f(n) SPACE)

NP subset NPSPACE (If a TM runs in f(n) TIME, it uses at most f(n) SPACE)

Hence, NP subset PSPACE (PSPACE = NPSPACE)

PSPACE subset EXPTIME