程序代写代做代考 algorithm Microsoft PowerPoint – lecture9 [Compatibility Mode]

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 L2P then also L1P

• If L1 P then also L2P

• 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
L2LOGSPACE then also L1LOGSPACE

reduction
R

Algorithm
for L2

x

instance
for L1

R(x)

instance
for L2

Yes
Yes

No
No

• If L2L then also L1 L

• If L1  L then also L2 L

• If L2 NL then also L1 NL

• If L1 NL then also L2NL

– 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 M12 and M23 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.