Complexity Theory
Past Paper
Reference
Credit:
@Dimitrios Los
TIME
P, NP, co-NP, completeness, UP
y2022p6q4
y2023p6q1
Hamiltonian cycle
y2023p6q2
pseudo one-way function
y2012p6q1
y2014p6q1
def, empty set
y2018p6q3
co-NP
y2019p6q4
y2017p6q2
y2016p6q1
UP
y2015p6q1
y2014p6q2
y2011p6q2
Space
L, NL, PSPACE, NPSPACE
y2022p6q3
y2020p6q4
Reachability
y2018p6q4
Reach, NL-complete under logarithmic-space reductions.
y2017p6q1
Difference in alphabet, binary vs unary
Hierarchy
y2002p6q12
TIME
y2015p6q2
SPACE