Complexity Theory
Alessandro Barenghi
Dipartimento di Elettronica, Informazione e Bioingegneria Politecnico di Milano
7 giugno 2021
Complexity theory: purpose and subjects
Complexity theory is used to classify problems according to how expensive in time/space is solving them
We will deal with problems which are:
With both domain and range over the naturals N Corresponding to the computation of a total computable function: each problem has afinitely described algorithm solving it infinitetime for any input
A bit of problem taxonomy:
Search problem: given an input x ∈ N to a problem corresponding to the computation of f (x), find
y = f (x), y ∈ N. Example: compute the square root of x.
Decision problem: given an input x ∈ N decide if x abides to some property f (x) : N → {>, ⊥}. Ex. Is x a perfect square?
Complexity classes
Complexityof computing the solution to a problem as a function of the input length n in base b > 1
Define the class (=set of problems) DTIME(f (n)) as the ones for which a deterministic TMtakes f (n) moves to compute the solution
NTIME(f (n)) class: a nondeterministic TMtakes f (n) moves to compute the solution
In general, relations between DTIME and NTIME are not well understood
Exception: DTIME(O(n)) ⊂ NTIME(O(n))
Analog classes exist for space complexity DSPACE(f (n)), NSPACE(f (n))
Complexity classes
Given f (n), can always build a problem not in DTIME(f (n)).
∀k ≥ 1 there is a problem ∈ DTIME(nk) and
∈ DTIME(n/ k−1)
Some notable time complexity classes are:
P =S
i≥1DTIME(ni), i ∈ N: “practically treatable” for any n NP =S
i≥1NTIME(ni), i ∈ N EXP =S
i≥1DTIME(2ni), i ∈ N PSPACE =S
i≥1DSPACE(ni), i ∈ N: NOT practically tractable in general, NP ⊆ PSPACE
P ⊆ NP ⊆ PSPACE ⊆ EXP, but P ( EXP
Open questions: P= NP, P? = PSPACE. Likely answer: No.?
NP - An alternate definition
It is possible to define a problem to be in NP in two ways
1 There is a nondeterministic TM which computes the solution to it in polynomial time
2 There is adeterministicTM which verifies that a solution for the problem is an actual solution in polynomial time
For decision problems: there is a deterministic TM which, given an element which makes the ND-TM accept, tests that is actually one of the elements which should make the ND-TM accept
Example: Exiting a binary branching labyrinth without a map:
1 A nondeterministic TM will find the poly-length exiting path, if any, taking all the branches in parallel
2 A deterministic TM, given the path, will verify that it actually exits from the labyrinth through walking through it
NP and complement classes
P and NP defined on decision problems, for simplicity.
A decision problem on the naturals = test if a natural belongs to some defined set = test if a string belongs to a language What about testing if the integer does notbelong to a set?
If recognizing if it belongs to the set ∈ P the problem is still
∈ P: swap accepting/rejecting states in the recognizing TM.
If recognizing if it belongs to the set ∈ NP, the problem is
∈ coNP: the class of problems for which (deciding if an elements belongs to) the complement of a given set is in nondet-poly time.
The “swap accepting/rejecting” does not work anymore: a TM terminates on a single accepting state, or when all paths reject
If I swap states, I’ll only checkoneof the old rejecting paths NP = coNP? Open question; Highly likely answer: no.
Computational reductions
A need tool to compare the complexity of two problems:
computational (aka Turing) reduction
Given two problems A and B, A reduces to B ifgiven an oracle for B I can solve A. Thus
A cannot be harder to solve than B B can be harder to solve than A
Therefore, A ≤T B (where T reminds it’s a Turing reduction) If A ≤T B and I make only a poly number of calls to the oracle for B when solving A, plus extra poly-time
computations
A reduces polynomially (or, Cook-reduces) to B
A ≤Tp B, since solving B also solves A with extra poly effort
CLASS-hardness and CLASS-completeness
Given a complexity class CLASS and a generic problem B, B is CLASS-hard iff:
∀A ∈ CLASS, A ≤Tp B
In other words, solving a CLASS-hard problem solves with extra poly effort all the problems in CLASS.
Given a complexity class CLASS and a problem B, B is CLASS-complete iff:
B ∈ CLASS and B is CLASS-hard
CLASS-complete problems are the “computationally hardest”
within a class
A taxonomy in NP – Assuming P 6= NP
NP-Hard problem: any problem such that I can poly reduce to it any problem in NP. Note, there may be non-decision
problems in this set.
NP-Complete class: problems such that all the problems in NP can be poly reduced to any of them. Conventially formulated as decision problems only
3-SAT,Graph coloring, Subgraph isomorphism, decoding random linear codes, syndrome decoding
NP-intermediate: essentially the complement of NPC to NP\P. Some problems here have sub-exponential solutions
Factoring ∈ DTIME(O(e(c+o(1))n
1
3log(n)23)), Discrete Logarithms
Graph isomorphism (proven in 2015, disproved in ’17, reproven in ’17 later on, should be O(2(log(n)3)), this time, for real)
Quantum Computing Model
A transition of a classical TM computes a constant time operation on a finite set of symbols from a finite alphabet An abstract quantum computing machine is a machine applying unitary transformations (gates) assumed to be constant time to a finite set of qubits
Complexity evaluated as a function of the (classical) input length n:
Time: evaluated as either the number of sequential gates (depth) or the total number of gates (O(depth×qubits)) Space: evaluated as number of involved qubits
A measurement of the result may not yield the same classical value if the computation is repeated → probabilistic
computation model
A primer on probabilistic computation
What is a randomized algorithm? We may randomize:
running time: Algorithm A runs in probabilistic poly time, i.e., with a certain probability it terminates in poly time
correctness: regardless of the running time, the algorithm returns the correct answer with probability p
We can solve problems, in expectation, if:
The running time is either deterministically or probabilistically polynomial, with P r(poly time) 12ink
The algorithm provides a corrects solution with a satisfactory probability, that is, either :
p ≈ 1
p is large enough to allow us to query the algo poly times and do majority voting. p = 12+21n would need exp. no. calls
Probabilistic computation classes (for TMs)
PP class: the problem is solved in DTIME(poly(n)) by an algorithm outputting the correct answer with Pr > 12
Not necessarily tractable:12+21n > 12
BPP class: the problem is solved in DTIME(poly(n)) by an algorithm outputting the correct answer with Pr > 12 + k
Tractable, for reasonable values of constant k, Typ. Pr = 23 RP class: the problem is solved in DTIME(poly(n)) by an algorithm outputting accept with Pr > 12 + k,if the solution is accept, but never accepting when it has to reject
ZPP class: the problem is solved in DTIME(poly(n)) by an algorithm which: gives a correct answer with Pr = 12, or answers “I don’t know” with Pr = 12.
Equivalent to an algo running on expected poly time, always giving correct answers (not straightforward)
Probabilistic computation classes (for TMs)
Probabilistic computation classes (for quantum computers)
Finally, we can define what is tractable by a QC
We consider the former abstract quantum machine model and define complexity as a function of the classical input length n BQP class: the problem is solved in DTIME(poly(n)) by a quantum machine which leaves a final state on which a measure yields theclassical correct answer with Pr > 12 + k Functionally analogous to BPP, but on a quantum computer We know BPP ⊆ BQP: a QC emulates a classical
probabilistic TM on poly-time algs, with poly-time overhead No sense in defining QP: cannot have a deterministic QC!
Relations between BQP and the other classes
coNP coNP- complete
Testing primality Multiplication
Problems with potential exponential speedup
Which speedups can we achieve?
Anything lying in NP \ P, and in BQP, or in coNP \ P, and in BQP → likely to gain exponential speedup
We have no general det. poly algorithm for A ∈ NP \ P Anything in P → likely not worth it: already poly time
Usually, solving problems in P on a QC is slower (due probabilistic computation and reversibility)
Outside BQP, inside PSPACE → no exponential speedup, but subexponential gains are possible
E.g. complexity goes down from O(2n) to O(2n2) Strong belief: NP-complete ∩ BQP = ∅
A quantum computer is not a nondeterministic TM!
3SAT, SubGI arenotgetting an exponential speedup
