Computer Science 456/656: Automata and Formal Languages

Spring 2013

Homework Assignment 5.

Due May 7, 2013

  1. Prove that the clique problem is NP-complete, by reduction of the independent set problem, which we already proved to be NP-complete, to the clique problem.
  2. Find a general grammar that generates the language consisting of all strings of the form anbncn.
  3. Let HALT be the halting problem (that is, the language of all binary strings of the form <M>x such that is the binary encoding of a Turing machine M which accepts x.)
    Let HALT-EMPTY be the empty halting problem, that is the language of all binary encodings <M> such that M accepts the empty string.
    Prove that HALT-EMPTY is undecidable by reduction of HALT to HALT-EMPTY.
  4. The Grader's Problem is the language consisting of all pairs of Pascal programs P1P2 such that P1 is equivalent to P2.
    Prove that the Grader's Problem is undecidable by reduction of HALT-EMPTY to the Grader's Problem.
  5. The 0/1 Factoring Problem is the set of all strings of the form <a>,<b> such that a and b are positive integers and a has a divisor which is between 2 and b.
    Using the fact that Primality is now known to be polynomial time, prove that the 0/1 Factoring Problem is co-NP.
    not co-NP complete. I made a mistake!
  6. A Boolean circuit is said to be of size k if it has no more than k gates, for some constant k. Clearly, the Boolean circuit problem, restricted to circuits of size k, is in Nick's Class, since it can be worked by one processor in constant time.
  7. A Boolean circuit is said to be wide if there is some constant k such that the circuit is constructed from any number of Boolean circuits of size k connected in parallel.
    Prove that the Boolean Circuit Problem, when restricted to wide circuits, is in Nick's Class.
  8. A Boolean circuit is said to be narrow if there is some constant k such that the circuit is constructed from any number of Boolean circuits of size k connected in series.
    Prove that the Boolean Circuit Problem, when restricted to narrow circuits, is in Nick's Class.
    (This is much harder than the problem for wide circuits.)

Back to Course Page