CS 456/656 Assignment 5

Due date: Tuesday, December 4, 2012, 4:00.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
  1. Prove that any language which is in the class NP-time is also in the class P-space.

  2. Prove that there is a Turing machine M, whose encoding has length n for some n, such that:
    1. With empty input, M halts.
    2. With empty input, M does not halt in the first 222n steps.
    Hint: you should use the fact that the halting problem is undecidable.

  3. Prove that the 0-1 factoring problem is both NP-time and co-NP-time, where the numbers are given to you as binary numerals.
    Hint: It is now known that primality is P-time. You may use this fact.

Back to Course Page