17

1. PS::=Languages/Problems that be solved in polynomial space.
2. PSPACE::=what the book calls PS.
3. Co_NP::={L:Language. complement(L) is in NP}.

   11 Additional Classes of Problems 469

   11.1 Complements of Languages in NP 470

   It is easier to guess positive examples and check them (problems in NP) than it is to to reject ALL possible examples (problems in co-NP).

   Exercise: draw Figure 11.1 from memory and then review your answer with the book.

   Ch 11.1 pp 470 -- Complements of Languages in NP

   What does it mean for a language to be closed under complementation?

   Not much! We are actually talking about classes of languages, not just a single language. Each language has it's complement:

   1. complement(L)::= the set of strings that are not in L.

      A class of languages is closed under complement if applying the complement operation gives us another language in the same class. For C:class_of_languages closed_under_complement(C)::= for all L:C(complement(L) in C).

      Ch 11 pp 470 -- Co-NP

      I understand that Co-NP is the complement of NP, but I was confused when the book said that if P = NP then Co-NP and NP are the same. Can you explain that.

      Common mistake: Co-NP is not the complement of NP! It is the collection of languages that complement languages in NP.

      Now the class of P languages is closed under complement. So if we could say

   2. P = co-P.

      So if P=NP then co-NP=co-P=P=NP!

      Ch 11.1 pp 470 -- co-NP

      So if P problems have polynomial run-times and NP-Complete problems have exponential run-times and above, what kind of run-times do non-P co-NP (co-NP-Complete?) problems have?

      11.1.1 The Class of Languages Co-NP 470

      Example 11.1 SAT, USAT, and TAUT

      11.1.2 NP-Complete Problems and Co-NP 471

      Theorem 11.2 NP=co_NP iff for some NP-complete L, complement(L) is NP

      The labels (Only-if) and (If) are switched in the proof (I think).

      Structure of Proof
      

   3. (above)|- (if): If NP=co_NP then for some NP-complete L, complement(L) is NP.
      Let
      1. NP=co_NP.
         
      2. (above)|-for some L, L is NP_complete,
         
      3. (ei, def)|-L is in NP,
         
      4. (hyp)|-L is in co-NP.
         
      5. (def)|-complement(L) is in NP.
      
      (Close Let )
      
      
   4. (above)|- (only_if): If some NP-complete L, complement(L) is NP then NP=co-NP.
      Let
      1. NP-complete L, complement(L) is NP.
      2. ...
      3. NP = co-NP iff NP in co-NP and co-NP in NP.

         You prove sets equal (A=B) in two steps (A in B) and (B in A).

         Prove NP in co-NP.
         Let

         1. L:NP,
         2. ...
         3. L in co-NP
         
         (Close Let )
         

         Prove co-NP in NP.
         Let

         1. L:co-NP,
         2. ...
         3. L in NP
         
         (Close Let )
         
      
      (Close Let )
      

      Diagram showing P, NP, co-NP, .....

      [ Complexity2.gif ]

      Note: Exercise 11.1.2 below gives us an example of a language that is in both NP and co-NP but not P -- given that a function like f exists. Locate the place in the above figure where you should put this problem.

      11.1.3 Exercises for Section 11.1 472

      ! Exercise 11.1.1 NP? complement! NP-complete?...

      I suggest you first try the *a exercise and check your answer against the books answer.

      An exercise are best done like this:
      

      1. Write down, very precisely the complement of the problem.
      2. Do one of the following
         Case
         1. Find an NP solution to the given problem.
         
         (End of Case)
         Case
         1. Find an NP solution to the complement of the given problem.
         
         (Close Case )
         
      3. Do one of the following:
         Case
         1. Prove the given problem NP-complete (reduction).
         2. Conclude that it is likely that the complement is not NP.
         
         (End of Case)
         Case
         1. Prove the complement to be NP-complete.
         2. Conclude the given problem is unlikely to be NP.
         
         (End of Case)
         Case
         1. State your best guess as to which if any is NP-complete without proof and loose a point or two.
         
         (Close Case )
         
      
      It is wise to pick an exercise where you have a feeling about what is reduced to what.
      
      1. TRUE-SAT
      2. FALSE-SAT
      3. DOUBLE-SAT
      4. NEAR-TAUT
      
      

      ! Exercise 11.1.2 trapdoor functions

      A trapdoor function can be evaluated quickly, but inverting it is a slow process. These are clearly useful in constructing encryption schemes... if they exist. Here they provide a counter example to the idea that a NP and co-NP problem has to be in P.

   11.2 Problems Solvable in Polynomial Space 473

   Ch 11.2 pp 473-478 -- Importance of Polynomial Space

   Is it better to have an algorithm that takes n-time and 2^n-space or n-space and 2^n-time to complete?

   iIt depends on the particular project/application. Think of a project or applicayion where you want it fast but can pay for more storage? Think up a project were memory is at a premium but the time to spare.

   11.2.1 Polynomial-Space Turing Machines 473

   Errata in footnote to page 473

   The last occurrence of "time" on the page should be "space".

   Ch 11.2 pp 476 -- PS in polynomial space

   What is the difference between Deterministic and Nondeterministic polynomial space? This was unclear to me.

   Ch 11.2.3 pp 476-478 -- Polynomial Space

   This section discusses deterministic and nondeterministic polynomial space. What is the difference between these polynomial space and the regular deterministc and nondeterminisic turing machines that we learn in Chapter 9.

   The only thing special about a space-bound TM and a normal one is that we can calculate how tape it needs for a given size of input. It can be either deterministic or non-deterministic -- just like an unbound TM.

   11.2.2 Relationship of PS and NPS to Previously Defined Classes 474

   Ch 11.2 pp 474 -- Theorem 11.3

   Could you please go through Theorem 11.3.

   Ch 11.2.2 pp 474-475 -- Theorem 11.3

   Can you explain the calculation that produces c^(1 +p(n)) in theorem 11.3.

   Theorem 11.3 PSPACE TM is EXP TIME TM

   
   Let
   
   
   1. (given)|-M is a polynomial-space-bounded TM with bound p(n).
   2. (goal): For some c, for all words w accepted with length n ( number of steps is bounded by c^(1+p(n)).

      Proof is a pumping lemma style proof. If it takes too long to accept a word of length n then the ID must repeat and so there must be a shorter accepting sequence.

      Key thought: if word w has n symbols then the tape available is p(n) long.

      So how many different tapes are there with p(n) symbols each with t =|\Gamma| possibilities.

      Answer: t^(p(n)).

      Where can the head be? Anywhere in the p(n) tape symbols.

      And assume: s= |Q| -- the number of states.

      Then only s*p(n)* t^(p(n)) possible IDs.

      Trick: set c=s+t and look at c^(1+p(n)).

      Prove it is > s*p(n)* t^(p(n)).

      Hence within c^(1+p(n)) steps an ID must repeat. So it either accepts earlier or not all in p(n) space.

   
   (Close Let )
   

   Ch 11 pp -- Factorial Time P-Space Possible?

   The c^(1+p(n)) term suggests that all things in PS/NPS can be completed in exponential time; does that mean that any algorithms which require factorial time are not in PS/NPS? Or is there a way to express factorials in terms of exponentials?

   Interesting...

   Theorem 11.4 PSPACE problem is EXP TIME

   11.2.3 Deterministic and Nondeterministic Polynomial Space 476

   Boolean reach(ID I, ID J, int m)

   Theorem 11.5 Savitch's Theorem: PSPACE = NPSPACE

   11.3 A Problem That Is Complete for PS 478

   Ch 11.3 PS-complete like NP-complete

   No one has ever been able to solve an NP-complete problem Is PS-complete the same?

   The problem with NP-complete problems is that they are solvable but they take a lot more time than you might at first expect. Further if we can find an fast solution to any of them then we have an fast solution to them all.

   PS-complete problems are similar. If we could solve a PS-complete problem in polynomial time than all PS problems can solved in polynomial time.

   11.3.1 PS-Completeness 478

   Definition of PS-complete

   Theorem 11.6 Collapsing hierarchies

   11.3.2 Quantified Boolean Formulas 479

   1. QBF::=quantified boolean formulas.

      QBF Syntax

   2. QBF::= "0" | "1" | "not" QBF | QBF operator QBF | "("quantifier variable")" "(" QBF ")".
   3. operator::= "^" | "\/".
   4. quantifier::= \all | \some.

      Example 11.7 of a QBF

      The meaning behind the expressions (for all x) (E) and (there exists x) (E) confuses me. They seem so very similar. Can you explain where the differences lie?

      QBF Semantics

      Define an evaluation function mapping each QBF into boolean values:
   5. eval::QBF->{0,1} where following,
      Net
      1. eval(0)::=0.
      2. eval(1)::=1.
      3. For QBF E, eval(not E)::= not eval(E).
      4. For QBF E1, QBF E2, eval(E1 ^ E2)::= eval(E1) and eval(E2).
      5. For QBF E1, QBF E2, eval(E1 \/ E2)::= eval(E1) or eval(E2).
      6. For QBF E, variable x, eval( (\all x)(E) ) ::= eval(E[x:=0]) and eval(E[x:=1]). Note1
      7. For QBF E, variable x, eval( (\some x)(E) ) ::= eval(E[x:=0]) or eval(E[x:=1]).

      
      (End of Net)
      
      

      11.3.3 Evaluating Quantified Boolean Formulas 480

      Ch 11 pp 479 -- Quantified Boolean formulas

      Example 11.8

      Evaluate QBF by induction/recursion.

      11.3.4 PS-Completeness of the QBF Problem 482

      Theorem 11.10 -- QBF is in PSA

      Show how to handle the 6 different syntactic forms of QBF. Completed in Exercise 11.3.5 below.

      Theorem 11.11 -- QBF is PS-complete

      Construct a polynomial time computable map from any given PS problem into QBF.

      Express a PS TM using booleans! The idea shouldn't be too surprising. Proving that it can be done took some ingenuity.

      Structure of Proof

      ---

      1. Encode IDs as boolean variables.
      2. Abreviation for quantifying over all variables in an ID.
      3. Formula = (\some start)(\some finish)(Starts ^ Next ^ Finishes).
      4. The QBF for Next takes a clever gimmick for dividing and conquering without doubling the size of the formula. YAGNI.

      ---

      Diagram showing PSPACE, P, NP, co-NP, .....

      [ Complexity3.gif ]

      11.3.5 Exercises for Section 11.3 487

      Exercise 11.3.1 Complete the proof of theorem 11.10

      *!! Exercise 11.3.2 Universal Regular expressions

      This is in GJ75.

      !! 11.3.3 The Shannon Switching Game

      GJ75 remark that many games have solutions that are expressed as QBF formula:
      1. For some winning move, for all replies from my opponent, there is a winning move, ....

. . . . . . . . . ( end of section 17) <<Contents | End>>

Next -- Randomization