Q: STRONGLY-CONNECTED
Proof:
A language B is NL-complete if
1. B є NL, and
2. every A in NL is log space
reducible to B.
We know that PATH is NL-Complete.
So we will construct a log space reduction from Strongly-connected to PATH. i.e
STRONGLY-CONNECTED <L PATH
Let say NTM M decides
STRONGLY-CONNECTED in O(logn) space. Functionality of M is as under
The nodes of G are the
configurations of M on w.
For configuration c1 and c2 of M
on w , (c1,c2) are the edges if c2 is the next possible configuration of M starting
from c1.
Node s is the start configuration
of M on w.
If machine reaches configuration
t then accept.
Now to show that this operation
has been performed in logarithmic time, we introduce a log space transducer
from <G,s,t> on input w. We describe G by listing its nodes and edges.
Listing of nodes is easy because each node is configuration of M on w and can
be represented in clogn space for some constant c. The transducer possibally
goes through all possible strings of length clogn.
Thus the STRONGLY-CONNECTED <L
PATH.
Q:
Pallindrome
M1 = “On input string w:
1. Scan across the tape and look
for 0s and 1s
2. Count number of 0s separately
3. Count number of 1s separately
4. compare both the counters if
both are equal accept, otherwise reject
the machine
countsthe number of 0s and, separately, the number of 1s in binary on the work
tape.The only space required is that used to record the two counters. In
binary, eachcounter uses only logarithmic space and hence the algorithm runs in
O(log n)space. Therefore, A є L.
Q:
Mult-SAT
----------------------------------------------------------------------------------------------------------------
Q: Clique reducibility to Half-clique
We give a polynomial time mapping
reduction from CLIQUE to HALF-CLIQUE.
The input to the reduction is a
pair (G, k) and the reduction produces the graph
(H)as output where H is as
follows. If G has m nodes and k = m/2, then H =G.
If k < m/2, then H is the
graph obtained from G by adding j nodes, each connected
to every one of the original
nodes and to each other, where j = m − 2k.
Thus, H has m + j = 2m − 2k
nodes. Observe that G has a k-clique iff H has a
clique of size k + j = m − k, and
so hG, ki 2CLIQUE iff hHi2HALF-CLIQUE.
If k > m/2, then H is the
graph obtained by adding j nodes to G without any
additional edges, where j = 2k −
m. Thus, H has m + j = 2k nodes, and so
G has a k-clique iff H has a
clique of size k. Therefore, hG, ki 2 CLIQUE iff
hHi2HALF-CLIQUE. We also need to
show HALF-CLIQUE 2NP. The certificate
is simply the clique.
Q: ISOMORPHIC…..
In
this question replace 1 with #....
Download : Click Here