Microsoft PowerPoint – lecture9 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 9, 2/13/18
Outline
• Invariant (Robust) Classes
• Reductions: polynomial time, log-space
• Composition of reductions
• Hardness and completeness
Relations
• L Í NL=coNL Í
Í P Í NP, coNP Í
Í PSPACE=NPSPACE Í
Í EXP Í NEXP Í
Í EXPSPACE=NEXPSPACE
Corollaries of Hierarchy Theorems
• P ¹ EXP , NP ¹ NEXP
• L Í NL PSPACE EXPSPACE
Reductions between Languages
• Languages L,L’ over alphabets ’
• Reduction from language L to L’ (notation L≤ L’):
• function R: * → ’* s.t. x *, x L iff R(x)L’
L L’
R* ’*
L ‘L
Complementation: R is also a reduction from to ‘L L
Reductions between Decision Problems
• Reduction from decision problem to ’
= reduction from L to L’
• Usually we ignore invalid encodings (since they are
efficiently recognizable and are irrelevant to the decision
problem). Want R to map Yes instances of to Yes
instances of ’ and No instances of to No instances of ’
Instances of Instances
of ’
Yes Yes
No No
R
Resource restrictions of reductions
• Restriction on resources (time, space) used by reductions
so that we can relate the complexity of the problems.
• Polynomial time reduction
• (notation: 1 ≤P 2 or L1 ≤P L2 )
• Log(arithmic) space reduction
• (notation: 1 ≤log 2 or L1 ≤log L2 ; some authors: L1 ≤L L2 )
• Every log-space reduction is also a polynomial reduction
( because LÍP , both for languages and functions)
Polynomial Reductions
reduction
R
Algorithm
for L2
x
instance
for L1
R(x)
instance
for L2
Yes
Yes
No
No
• If L2P then also L1P
• If L1 P then also L2P
• If L2 NP then also L1 NP
• If L1 NP then also L2 NP
P- Reductions compose: L1 ≤P L2 and L2 ≤P L3 L1 ≤P L3
1 P 2 1 P 2Complementation: L L L L
Log-space Reductions: If L1 ≤log L2 and
L2LOGSPACE then also L1LOGSPACE
reduction
R
Algorithm
for L2
x
instance
for L1
R(x)
instance
for L2
Yes
Yes
No
No
• If L2L then also L1 L
• If L1 L then also L2 L
• If L2 NL then also L1 NL
• If L1 NL then also L2NL
– Used L for the class L (LOGSPACE), so we don’t confuse with languages
• Only problem: R(x) may well have size >> log|x|.
x
R(x)
• We don’t want to generate R(x) explicitly, otherwise algorithm will not be
log-space
• Generate one symbol of R(x) at a time as needed
• Run M2 and keep track of position of its input head (on a separate tape)
– In each step when it needs an input symbol (=output symbol of MR), run
MR from its initial configuration without writing on its output, keep a count of
the #output symbols generated until it generates the desired symbol. Make
the move of M2 (i.e. update state, tape cells, head positions), erase work
tapes of MR and iterate
Work tapes of MR Work tapes of M2
M1
MR M2
logspace TM MR for the reduction and logspace TM M2 for L2
logspace TM M1 for L1
output of MR =
input of M2
Input tape
Analysis
• Space of combined TM = sum of the spaces + space for
position of input head of M2 + a counter (to count output
symbols generated by MR in a step).
• MR log-space halts in time for some c
| R(x)| ≤ clogn bits for the position and counter
• Space of combined TM M1 = O(logn)
clogn2
clogn2
Log Space reductions compose
• L1 ≤log L2 and L2 ≤log L3 L1 ≤log L3
• Same construction:
• Combine the log-space TMs M12 and M23 for the two
reductions, but do not write explicitly the output of the
first reduction but only generate it one symbol at a time,
as needed.
Hardness and Completeness
• A Language L or decision problem is hard for
a class C, or C–hard, under a type of reduction
(eg. polynomial or log-space reduction) if every
problem in the class C reduces to it.
• It is complete for a class C, or C–complete, under
a type of reduction if
1. it belongs to C
2. it is C–hard under the reduction.
Hardness and Completeness
• NP-complete: usually we use p-reductions for NP
and for classes above P. It turns out that the usual
NP-complete problems are complete also under the
more restrictive log-space reduction.
• NL-complete, P-complete : usually we use log-
space reductions for P and classes below it
• Reason: All nontrivial problems in P are complete
under p-reductions (nontrivial means there is a yes
instance and a no instance), so p-reductions do not
give any useful information inside P
Properties of completeness
• Intuitively, Complete problems are the hardest in
the class
• If L is complete for a class C (eg. NP) under
polynomial reductions then C Í P LÎP
• If L is complete for a class C (eg. P or NL) under
logspace reductions then
C Í LOGSPACE L Î LOGSPACE
Properties of completeness
• Compositions of reductions implies:
• If L1 is hard for a class under p-reductions and L1
≤P L2 then L2 is also hard for the class
• If L1 is hard for a class under logspace-reductions
and L1 ≤log L2 then L2 is also hard for the class
• Complementation implies:
• coC-complete problems = complements of C-complete
problems.
• eg. coNP-complete problems = complements of NP-
complete problems.