Finally, we must show that the language is not in P.
We can show that if it were in P, then with n tests for
membership in the language, we could binarysearch to find the exact
value of f^{1}(x).
If one test takes time that is polynomial in n, then n
times that amount is also polynomial in n.
Start by testing the pair (x,2^{n1}), i.e., the rough midpoint
in the range of nbit integers.
If the answer is ``yes,'' next test (x,2^{n2}); if the answer is
``no,'' test (x,3*2^{n2}) next.
In this manner, we can establish one bit of f^{1}(x) at each
test, and after n tests, we know f^{1}(x) exactly.
Return to Top
Solutions for Section 11.3
Exercise 11.3.2
Suppose M is a TM with polynomial space bound p(n), and w is
an input to M of length n.
We must show how to take M and w, and write down, in polynomial
time, a regular expression E that is Sigma* if and only if M
does not accept w.
Technically, this construction reduces L(M) to the complement of
the set in question, that is, to the set of regular expressions that are
not equivalent to Sigma*.
However, an easy consequence of Theorem 11.4 is that, since a
deterministic, polynomialtime TM can be made to halt, PS is
closed under complementation; just change the accepting states to
halting, but nonaccepting states, add an accepting state, and make every
halting, nonaccepting state transfer to that accepting state instead of
halting immediately.
Thus, we could assume that M is actually a TM for the complement of
the language L in PS in question.
Then, we are actually reducing L to the language of regular
expressions equivalent to Sigma*, as requested.
To construct regular expression E, we shall write E = F + G +
H, where the three subexpressions E, F, and H
define sequences of ID's of M that do not ``start right,'' ``move
right,'' and ``finish right,'' respectively.
Think of an accepting computation of M as a sequence of symbols that
are the concatenation of ID's of M, each preceeded by a special marker
symbol #.
The alphabet Sigma for E will be # plus all the tape and state
symbols of M, which we can assume without loss of generality are
disjoint.
Each ID is exactly p(n)+1 symbols long, since it includes the
state and exactly p(n) tape symbols, even if many at the end are
blank.

H: Finishes wrong.
M fails to accept if the sequence has no accepting ID.
Thus, let H = (Sigma  Qf)*, where Qf is the set of
accepting states of M.

F: Starts wrong.
Any string in which the first p(n)+2 symbols are not #, q_0
(the start state),
w, and p(n)  n blanks, is not the beginning of an accepting
computation, and so should be in L(E).
We can write F as the sum of the terms:

(Sigma{#})Sigma*, i.e., all strings that do not begin with #.

Sigma(Sigma{q_0})Sigma*, i.e., all strings that do not have
q_0 as their second symbol.

Sigma^{i+1}(Sigma{a_i})Sigma*, where a_i is the ith
position of w.
Note Sigma^k stands for Sigma written k times, but this
expression takes only polynomial time to write.

Sigma^{i}(Sigma{B})Sigma*, for all n+3 <= i <=
p(n)+1.
Here, B represents the blank, and this expression covers all
strings that fail to have a blank where the first ID must have one.
Note that these terms require us to write Sigma as many as p(n)+1
times, but that still takes only polynomial time.
Also, there are polynomially many terms, so the total work is
polynomial.

(Sigma + epsilon)^{p(n)+1}.
This term covers all strings that are shorter than p(n)+2
symbols, and therefore cannot have an initial ID, regardless of the
symbols found there.
As in the previous set of terms, the time taken to write this term is large,
but polynomial.

G: moves wrong.
We need to capture all strings that have some point at which symbols
separated by distance roughly p(n) do not reflect a move of M.
The idea is similar to that used in Cook's theorem (Theorem 10.9).
Each position of an ID is determined by the symbol at that position in
the previous ID and the two neighboring positions.
Thus, G is the sum of terms
(Sigma*)UVW(Sigma^{p(n)})X(Sigma*), where
U, V, W, X are four symbols of Sigma such that if UVW were
three consecutive symbols of an ID of M (U may be # if the ID
is just beginning, and W may be # if the ID is ending), then
X would not be the symbol in the same position as V
in the next ID.
For example, if none of U, V, W are a state, then X could
be any symbol but V.
Again, we can write this large expression in polynomial time, even though it
requires us to write Sigma p(n) times.
If M accepts w, then there is some accepting computation, and the
string representing that computation fails to match any of the regular
expressions described above.
Thus, E != Sigma*.
However, any string that is not an accepting computation of M on w
will surely fail meet one of the conditions ``starts wrong,'' ``moves
wrong,'' or ``finished wrong,'' and therefore will be in L(E).
Thus, if M does not accept w, then E = Sigma*.
Return to Top
Solutions for Section 11.5
Exercise 11.5.1(a)
A simple way to to observe that 9  11 = 2, and 2 modulo 13 is 11,
since 13 2 = 11.
Or, we may treat the subtraction as addition of a negative number, say
that 11 modulo 13 is 2, and 9 + 2 modulo 13 is 11.
Exercise 11.5.1(c)
We need to compute the inverse of 8 modulo 13.
Exploring the possibilities, from 2 to 12, we find that 8*5 = 40, which
is 1 modulo 13.
Thus, 1/8 = 5 modulo 13, and 5/8 = 5*5 = 25 = 12 modulo 13.
Thus, 5/8 = 12.
Exercise 11.5.3(a)
From the table of Fig. 11.9, we see that 2*2 = 4, 3*3 = 2, 4*4 = 2,
5*5 = 4, and 6*6 = 1.
We also know that 1*1 = 1.
Thus, 1, 2, and 4 are the quadratic residues modulo 7.
Return to Top