CS 456/656 Assignment 5

Do not turn this assignment in.
  1. The 0/1 version of the integer factoring problem is as follows.
    Given the numerals for two positive integers, n and m, does there exist a factor of n which is in the range 2..m?
    1. Prove that the 0/1 integer factoring problem is in the class P-TIME if n and m are given as unary numerals.
    2. Prove that the 0/1 integer factoring problem is in the class NP-TIME if n and m are given as binary numerals.
    3. Prove that the 0/1 integer factoring problem is in the class co-NP-TIME if n and m are given as binary numerals.
      Hint: it has recently been proved that primality is in the class P.
  2. Which of the following 0/1 problems are known to be P-time? Which are known to be NP-complete? Which are known to be decidable? Undecidable?
    1. Linear programming.
    2. Integer programming. (The same as linear programming, but restricted to integers.)
    3. The Post correspondence problem.
    4. The 0/1 traveling salesman problem.
    5. Ambiguity of a context-free grammar. Given a context-free grammar, is it ambiguous?
    6. The Boolean circuit problem, also known as the circuit evaluation problem, where the only gates allowed are AND, OR, and NOT gates.
    7. Given one graph, is it planar?
    8. Given two graphs, G and H, does G contain a subgraph isomorphic to H?
    9. Given a graph G, is G 2-colorable?
    10. Given a graph G, is G 3-colorable?
    11. Given a graph G and a number k, is G k-colorable?
    12. Finally, an easy one. Consider the game, "Push Pebble." Given a directed graph G, where one of the nodes is designated to be the Finish node, and every other node is colored either red or black. A pebble is initially placed on one of the nodes. The rules of Push Pebble are as follows.
      There are two players, Red and Black. Black is trying to cause Red to lose.
      If the pebble is on a Red node, Red must move it to another node by following one directed edge.
      If the pebble is on a Black node, Black must move it to another node by following one directed edge.
      If the pebble is on the finish node, Red wins.
      If the pebble reaches a node with no out-edges that is not the finish node, Red loses.
      If the game goes on forever, Red loses.
      Put another way, the problem is, given such a game and given an initial position of the pebble, does Red have a winning strategy?
  3. Let F be a function from binary strings to binary strings, such that, for each binary string w, there is a Turing Machine T_w which computes F(w). Can you conclude that F is computable? Why or why not?
  4. Define a 2-PDA to be a machine that is just like a PDA, except that it has two stacks. (It still has one input file.) Prove that, for any RE language L, there is some 2-PDA that accepts L.
  5. We say that a real number is algebraic if it a root of any polynomial with integral coefficients. For example, any root of an integer is algebraic.
    True or false: "For any algebraic number x, there is a machine E_x which runs forever, writing the decimal expansion of x."
  6. Let us suppose that we only care about approximating real numbers to d decimal places, where d is some fixed positive integer.
    True or false: "For any real number x, there is a machine M_x which computes a number which approximates x with an accuracy of at least d decimal places."
  7. "x or not x," is an example of a tautology. Prove that the set of tautologies is co-NP-complete.

Back to Course Page