
CSC 656 Graduate Assignment.
Due date, May 8, 2003, 11:30 AM.
All assignments must be handwritten
(not typed or printed from a computer file)
in your own handwriting, on 8.5 by 11 inch paper. Write your name on
each sheet, and do not fold the pages or crimp the corners.
Turn the pages in to me on the due date.
-
Work Exercises 1, 2, and 4.
-
Work Exercise 14.11 on page 523 of your textbook.
-
A public-private cryptography system could be built
by making use of function f such that f is easy, but
f -1 is hard. (RSA encryption assumes that multiplication
is easy, but factoring is hard.)
Prove that, if there exists a polynomial time function f such that
f -1 is not polynomial time,
then P is not equal to NP.
Clarification.
You may assume that both the domain and range of f are the set of all
binary strings, i.e., strings over the alphabet {0,1}.
If f is both one-to-one and onto, there is no confusion. But what if f
is neither one-to-one nor onto? In this case, we phrase the problem
this way:
"Suppose that f is a polynomial time function. Suppose that
there is no polynomial time function g which satisfies the following
conditions:
-
For any string y, if y is in the range of f, then f(g(y)) = y.
-
For any string y, if y is not in the range of f, then g(y) is the empty
string.
Then P is not equal to NP."
-
Work Exercise 1.

Back to
Course Page