http:^^www.cs.washington.edu^education^courses^431^96s^bboard.shtml

来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 1,486 行 · 第 1/4 页

possible to reply to them.

-jayram.
-- 
Jayram S. Thathachar                  [e-mail]
Department of CSE              http://www.cs.washington.edu/homes/jayram
University of Washington              [phone] (vox)
Box 352350, Seattle, WA 98195         [phone] (fax)
<hr size=4><a name="833507671001">Date: Thu, 30 May 1996 18:54:27 -0700 (PDT)
From: <b>Larry Roske &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>HW #5 #7 part (3)</b>
</a>

The hint suggests using the TM M_SAT as a subroutine to
determine if x1=0 or x1=1 is &quot;part&quot; of a satisfying assignment.

Since M_SAT accepts strings w in SAT, and SAT consists of
formulas with satisfying assignments for all variables,
can't we use M_SAT to test for a particular assignment to all of the
variables at one time, e.g. x1=0, x2=1, x3=0, etc.?

Ah ha! I think this is because we would have to try each
permutation of assignments which would create an exponential
time computation?

--Larry

<hr size=4><a name="833509703001">Date: Thu, 30 May 1996 19:28:16 -0700 (PDT)
From: <b>Jayram Thathachar &lt;[e-mail]&gt;</b>
To: Larry Roske &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>Re: HW #5 #7 part (3)</b>
</a>

On Thu, 30 May 1996, Larry Roske wrote:

&gt; The hint suggests using the TM M_SAT as a subroutine to
&gt; determine if x1=0 or x1=1 is &quot;part&quot; of a satisfying assignment.
&gt; 
&gt; Since M_SAT accepts strings w in SAT, and SAT consists of
&gt; formulas with satisfying assignments for all variables,
&gt; can't we use M_SAT to test for a particular assignment to all of the
&gt; variables at one time, e.g. x1=0, x2=1, x3=0, etc.?
&gt; 
&gt; Ah ha! I think this is because we would have to try each
&gt; permutation of assignments which would create an exponential
&gt; time computation?
&gt; 
&gt; --Larry
&gt; 
&gt; 

That's right. BTW, for those of you who were there during the office 
hours, the general definition of self-reducibility that I gave is 
completely wrong. I said that L is self-reducible if there is a poly-time 
reduction f such that x \in L iff f(x) \in L *and* |f(x)|&lt;|x|.

The correct definition is that L is self-reducible if there is a poynomial
time algorithm that can use the subroutine P for L as a black-box but any
calls P(y) made to P must use a y smaller in length than x. 

What follows is an explanation of why the definition I gave is wrong and 
is irrelevant to the hw problem in question. 

The definition that I gave is something else. If you think about it, by
applying f repeatedly, that is, let y=f(f(...(x)...)) so that y becomes
small enough, in constant time I can determine if y is in L and
conclude if x is in L. Computing y takes only polynomial time since I have
to apply f at most |x| times so L must be in P if it is self-reducible.

-jayram.



<hr size=4><a name="833512165001">Date: Thu, 30 May 1996 20:09:20 -0700 (PDT)
From: <b>Jayram Thathachar &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>hint for UHAMPATH</b>
</a>

Let's see. The only help I can give here is the following. This is a hint 
if you are using HAMPATH to reduce to UHAMPATH.

Let G' be the undirected graph obtained from G.
Suppose we want to make sure that in G', when entering a
vertex u, we always do so from a vertex x such that x-&gt;u is an edge in 
G. And while leaving u, we always use a vertex y such that u-&gt;y is an edge 
in G. Can you enforce this condition by adding extra vertices and making 
sure that any hamiltonian path in G' must obey this rule?

-jayram.
--
Jayram S. Thathachar                  [e-mail]
Department of CSE              http://www.cs.washington.edu/homes/jayram
University of Washington              [phone] (vox)
Box 352350, Seattle, WA 98195         [phone] (fax)



<hr size=4><a name="833512652001">Date: Thu, 30 May 1996 20:17:28 -0700 (PDT)
From: <b>Jayram Thathachar &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>hw4</b>
</a>

On the problem of P being closed under star, two of you came up with a
nice observation of what the fill-in-the-table algorithm was doing and
I thought I'd share it with you. 

Let L be the language in P and we want to show that L^* is in P. For an
input w=a_1 a_2 ... a_n, suppose we define a directed graph G on
{1,2,...,n+1} as follows: there is an edge from i to j iff a_i ... a_{j-1}
is in L. Then, 
   w is in L^* iff there is a path from 1 to n+1 in G.

The table algorithm that I gave in the solution set was just doing bfs on 
this graph.

--
Jayram S. Thathachar                  [e-mail]
Department of CSE              http://www.cs.washington.edu/homes/jayram
University of Washington              [phone] (vox)
Box 352350, Seattle, WA 98195         [phone] (fax)


<hr size=4><a name="833520727001">Date: Thu, 30 May 1996 22:32:04 -0700
From: <b>fineman@grizzly (Dan Fineman)</b>
To: cse431@cs
Subject: <b>A little end-of-the-quarter thought</b>
</a>


Every Horse has an Infinite Number of Legs (proof by intimidation):

Horses have an even number of legs.  Behind they have two legs, and in
front they have fore-legs.  This makes six legs, which is certainly an
odd number of legs for a horse.  But the only number that is both even
and odd is infinity.  Therefore, horses have an infinite number of
legs.  Now to show this for the general case, suppose that somewhere,
there is a horse that has a finite number of legs.  But that is a
horse of another color, and by the [above] lemma [&quot;All horses are the
same color&quot;], that does not exist.
 
<hr size=4><a name="833573118001">Date: Fri, 31 May 1996 13:05:12 -0700
From: <b>jayram@hobbes (Jayram Thathachar)</b>
To: cse431@cs
Subject: <b>solutions for the 3-COLOR and UHAMPATH</b>
</a>

It looks like I'll get to them after the office hours. Bear
with me for this inconvenience. I have the solutions for
the 4th and 7th problem ready.
-jayram.
<hr size=4><a name="833587822001">Date: Fri, 31 May 1996 17:10:17 -0700
From: <b>jayram@hobbes (Jayram Thathachar)</b>
To: cse431@cs
Subject: <b>hot off the oven</b>
</a>

Solutions to the hw will be available outside Larry's door in about
15-20mts. Your hws should have been handed in by now. I'll also
e-mail the solutions to 3-COLOR and UHAMPATH soon and finally
everything should be on the web later this evening.
-jayram.
<hr size=4><a name="833589342001">Date: 31 May 1996 17:14 PDT
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>Midterm solution</b>
</a>

a few copies will also be available outside my door, and it should be 
on the web already.
<hr size=4><a name="833590988001">Sender: [e-mail]
Date: Fri, 31 May 1996 18:03:03 -0700
From: <b>Jayram Thathachar &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>hw5 solutions</b>
</a>

Solutions to hw5 are available outside Larry's door.
-jayram.

-- 
Jayram S. Thathachar                  [e-mail]
Department of CSE              http://www.cs.washington.edu/homes/jayram
University of Washington              [phone] (vox)
Box 352350, Seattle, WA 98195         [phone] (fax)
<hr size=4><a name="833605482001">Sender: [e-mail]
Date: Fri, 31 May 1996 22:04:36 -0700
From: <b>Jayram Thathachar &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>solutions to 3-COLOR and UHAMPATH</b>
</a>

For those of you who were unable to pick up the solutions outside
Larry's door.
********************************************************************
Solution sketches to 3-COLOR and UHAMPATH
********************************************************************
3-COLOR is NP-complete:

3-COLOR is in NP via a verifier that, in polynomial time, using a
coloring of the vertices of the  graph as a certificate, can verify
that the coloring is a valid 3-coloring of G.

We will reduce 3CNF-SAT to 3-COLOR. Let \phi be a 3-CNF formula.
The graph that we build in polynomial time has the vertex set
{T,F,O} \union Set of literals \union Set of Clauses \union other
vertices.

Here are the edges in G, classified by their type:

         O
(a)     /\
       /  \
      /    \
     /      \
    /--------\
    T        F


(b) For each variable x:

        O
        /\
       /  \
      /    \
     /      \  _
  x /--------\ x


(c) (The OR-gadget) For each clause C = p \or q \or r

O___________C_____________F
|           /\
|          /  \
|         /    \
|        /      \
|       /--------\
|       |        |
|_______|        |
        /\       |
       /  \      |
      /    \     |
     /      \    |
    /--------\   |
    |        |   |
    |        |   |
    |        |   |
    p        q   r


In any valid 3-coloring, because of edges of type (a), the vertices T,
F and O get the 3 different colors. Let the colors that they get
itself be named T, F and O. Therefore, each vertex gets colored T, F
or O in any legal 3-coloring.

Because of edges of type (b), for any variable x, x and not(x) get
different colors in {T,F}. Thus, a legal 3-coloring can always be used
to define an assignment of 0-1 values to the variables.

Finally, the OR-gadget satisfies the following property:
Suppose in the OR-gadget corresponding to the clause C=p \or q \or r,
p, q, and r are each constrained to get colors from {T,F}. Then,

   there is a legal 3-coloring of the OR-gadget with the clause
   getting colored T iff at least one of p, q, r is colored T.

This can be checked by trying out the various combinations of color
assignments to the nodes in the gadget. (You may find it easier to work
with the OR-gadget given in the book for 2 literals and then get it to
work for 3).

Thus the formula is satisfiable iff every clause is satisfied by some
assignment iff there is a legal 3-coloring of G.

*****************************************************************

UHAMPATH is NP-complete

To show that UHAMPATH belongs to NP, the verifier takes the encoding
of hamiltonian path as a certificate and verifies that the certificate
indeed corresponds to a hamiltonian path in the input graph.

We will reduce HAMPATH to UHAMPATH as follows:
Suppose &lt;DG,s,t&gt; is an instance of HAMPATH. Let DG=(V,E)
We will create a undirected graph UG as follows:
The vertex set for UG is {v_i, v_m, v_o : v \in V} U {s',t'}

Informally, we will force any hamiltonian path between s' and t'
in UG to always correspond to a directed path in G (the subscripts for
the vertices refer to ``in'', ``middle'' and ``out'').

The edges for UG are

(a) For each vertex v in V,

     v_i ----- v_m ------ v_o

(b) For each edge u--&gt;v in E,

    u_o ----- v_i

(c) An edge s'----s_i and an edge t_o----t'

Claim: There is a hamiltonian path in DG from s to t iff there is
hamiltonian path from s' to t' in UG.
Proof: One direction is easy. Given a hamiltonian path in DG, we can
easily construct a hamiltonian path in UG. For example, if
s--&gt;a---&gt;b---&gt;t was the hamiltonian path in DG, the hamiltonian path
in UG is

   s'--s_i--s_m--s_o--a_i--a_m--a_o--b_i--b_m--b_o--t_i--t_m--t_o--t'

Now for the other direction. In any hamiltonian path in UG, for each
vertex v of DG, the vertices v_i, v_m, v_o must occur consecutively as 
v_i, v_m, v_o or as v_o, v_m, v_i because v_m is an interior vertex in
the path and v_m is connected to v_i and v_o only.
Because the path begins with s', the initial segment must be
s'--s_i--s_m--s_o. There are no edges from v_o to u_o in UG, for any
vertices v and u in DG, so the only way this path can be extended to a
hamiltonian path in UG is for it to have the form

    s'--s_i--s_m--s_o--(A1)--(A2)-- ... --(Ak)--t_i--t_m--t_o--t',

where each (Aj) is an abbreviation for the (sub)path v_i--v_m--v_o for
some vertex v in DG. Moreover, for each vertex v of DG, there is
exactly one j such that (Aj) corresponds to v. Suppose aj is the
vertex in DG corresponding to (Aj).

This can easily be transformed to a hamiltonian  path in DG:

       s--&gt;a1--&gt;a2--&gt; ... --&gt;a_k--&gt;t

-- 
Jayram S. Thathachar                  [e-mail]
Department of CSE              http://www.cs.washington.edu/homes/jayram
University of Washington              [phone] (vox)
Box 352350, Seattle, WA 98195         [phone] (fax)
<hr size=4><a name="833606680001">Sender: [e-mail]
Date: Fri, 31 May 1996 22:24:36 -0700
From: <b>Jayram Thathachar &lt;[e-mail]&gt;</b>
To: cse431@cs
Subject: <b>class web</b>
</a>

The solutions to hws 4 and 5 are on the class web as well. 
Good luck with the final!!!
-jayram.

-- 
Jayram S. Thathachar                  [e-mail]
Department of CSE              http://www.cs.washington.edu/homes/jayram
University of Washington              [phone] (vox)
Box 352350, Seattle, WA 98195         [phone] (fax)

</pre>
</body>
<hr>
<hr>
<address>
[e-mail]	
(Last Update: 
   <!-- see man strftime for full formatting options-->
  03/26/96)
</address>

</html>