Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!rpi!dali!uakari.primate.wisc.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu!apple!rutgers!mcnc!duke!grad19!srt
From: srt@grad19.cs.duke.edu (Stephen R. Tate)
Newsgroups: comp.theory
Subject: Re: SAT in _Computers & Intractability_
Keywords: SAT satisfiability Cook boolean NP complete P
Message-ID: <19971@duke.cs.duke.edu>
Date: 1 Jun 90 15:10:05 GMT
References: <7341@ccncsu.ColoState.EDU>
Sender: news@duke.cs.duke.edu
Lines: 54

Before I say (type) anything, let me say that it has been a while since
I read Garey and Johnson, so this is all by memory (and I don't have a copy
so I can't check easily).

In article <7341@ccncsu.ColoState.EDU>, ld231782@longs.LANCE.ColoState.EDU (Lawrence Detweiler) writes:
> Their attention to the polynomial time requirement is confined to a paragraph
> on p. 44, where they claim that
> 
>   The polynomial boundedness of this computation will follow immediately
>   once we show that Length(F(X)) is bounded above by a polynomial function
>   of N...
> 
> where N = Length(X).  Quite to the contrary, this result does not follow
> "immediately".  ....                                         To the
> author's credit, they note that construction of the transformation
> "amounts to little more than filling in the blanks" in a formula... 

This last part you mention is clearly the important statement.  I think
it is a fair to make the assumption that the reader will think for him/herself.
Clearly, the problem of writing down the boolean formula is a simple
"fill in the blanks" problem, and as long as the output is not too large,
then it can be computed quickly (I'd even venture to guess that the time
is linear in the output size....).  In fact, the conversion to the formula
is so simple it is even in logspace, not just polynomial time.

>                               Using the fundamental theorem of counting,
> and observing that the Q index ranges through P(N) (the variables R and V
> are constants, as noted in the text), H through P(N)^2, and S the same,
> it can be stated instead that
> 
> |U| < K1*P(N)^5
> 
> where K1 is some constant.

Now this is the real reason I posted... I can't believe you really said
this!  Taking what you said above, the number of states is P(N)+P(N)^2+P(N)^2,
plus some constant stuff thrown in.  Now why do you start adding exponents?
Clearly this sum is less than 3P(N)^2 for even small values of N.  In
other words,  |U| < c*P(N)^2 for some constant c.  You go on to add
exponents again in your posting....  the basic rule is as follows,
if you are adding polynomials, the degree of the sum is the MAXIMUM of
the degrees of polynomials you are adding, NOT the sum of the degrees.

> I was most impressed with Garey and Johnson's development of SAT up to p. 44
> and am most chagrined with it afterwards.  I look forward to learning of
> other's opinion on the matter in general and how appropriate my comments are
> in particular.

I don't remember thinking anything about it really.... of course I had
seen the same proof in about 3 other places and in about 4 classes before
I read it in Garey and Johnson....

Steve Tate			ARPA:  srt@duke.cs.duke.edu
				UUCP: ..!decvax!duke!srt