Path: utzoo!yunexus!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!mailrus!ncar!boulder!ccncsu!longs.LANCE.ColoState.EDU!ld231782
From: ld231782@longs.LANCE.ColoState.EDU (Lawrence Detweiler)
Newsgroups: comp.theory
Subject: SAT in _Computers & Intractability_
Keywords: SAT satisfiability Cook boolean NP complete P
Message-ID: <7341@ccncsu.ColoState.EDU>
Date: 1 Jun 90 04:02:34 GMT
Article-I.D.: ccncsu.7341
Sender: news@ccncsu.ColoState.EDU
Reply-To: ld231782@longs.LANCE.ColoState.EDU (Lawrence Detweiler)
Organization: Engineering College, Colorado State University
Lines: 139

-----
a Guide to the Theory of NP Completeness_ contains a version of Cook's
satisfiability theorem for their "slightly nonstandard" NDTM model.  For
this construction they show that (paraphrased)


1. There is a polynomial time algorithm that computes F(X), the function that
converts any particular NDTM problem to to an instance of SAT, and

2. That instance of SAT is satisfiable in all and only those cases of "input"
X for which the particular NDTM is accepting,


thus fulfilling the requirements of polynomial transformation (p. 34).

I respectfully submit that while their elaborate and "complicated" (but
necessarily so) demonstration of the second demand above leaves nothing
to be desired, their treatment of the first point is less rigorous,
perhaps even to the point of unacceptability and error.

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".  For example, the solution to the _optimized_
Travelling Salesman problem is always bounded in size by a polynomial
function of the length of the input, but in no way can this be construed
to imply therefore the computation occurs in polynomial time!  To the
author's credit, they note that construction of the transformation
"amounts to little more than filling in the blanks" in a formula, but it
seems some further words are in order to adequately convince the reader to
share their own confidence.

However, it is the close of this paragraph that supplies the most material
for confusion and perhaps even disbelief, where they state that

|U| = O(P(N)^2)

and likewise for C.  Or, to paraphrase, the cardinality (size) of the set of
all boolean variables in the SAT construction equals an order of growth of
P(N)^2, where P(N) is the time bound on the algorithm (more specifically the
NDTM) being transformed.

From whence came this?  The application of the syntax appears to be as
nonsensical as the cliche of comparison of apples and oranges: they are
relating a measure of the size of "input", in units of data, to the time
complexity of an algorithm, in units of time.  That this is incongruous
is evident from an examination of other parts of the chapter, where they
carefully avoid this obscure comparison with rigorous separation of
description of the properties of complexity of data vs. of time, such as
at the close of the proof of Lemma 2.1 (p. 35).

Moreover, even if the literal interpretation of the statement is relaxed,
its vague meaning that the size of these SAT sets is somehow equivalent to
the square of the time bound on the algorithm under conversion is wholly
false.

Take |U|, the boolean variables in the SAT construction, enumerated in
Fig. 2.7 (p. 40).  Since only the polynomial nature is at stake, only the
leading power of the range of all the variables Q (state), H (head), and S
(symbol) need be considered.  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.

|C|, the clauses in the final expression, is more complicated.  Derived
mostly from Fig. 2.9 (p. 43), following is a list of the degree that each
clause group contributes:

G1: 1
G2: 2
G3: 2
G4: 1
G5: 0
G6: 2
   ---
    8

so

|C| < K2*P(N)^8

where K2 is some constant.  Hence, using their function

Length[F(X)] = |U|*|C|

as a "reasonable" length of the conversion to the SAT problem, then

Length[F(X)] < K3*P(N)^13

where K3 is some constant.  If their argument about the relationship of
length and complexity holds here, this shows the conversion of the problem
to SAT can take place in polynomial time, satisfying the time requirement
for polynomial transformation.

Strangely, the authors give the exact number of clauses for many of the
groups in the text, possibly with the intention of using them later in
a similar manner as above, but no such reference can be found.



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.


P.S.

- I would be interested in the correlation of any of this to Cook's original
  version of the theorem.  I assume he used a different model of NDTM and,
  if so, time constraints would probably vary significantly (although still
  polynomially).

- On p. 30, the authors write, "The reader may find it an interesting
  exercise to verify the equivalence of our model to these ["more standard"
  NDTM versions] with respect to polynomial time."  To do so would require
  showing that their NDTM version can "recognize a language" in polynomial
  time IFF the other can.  How close is this to being intuitively obvious?
  This seems like too significant a point to relegate to a parenthetical
  remark and delegation of derivation to the reader.

- Also, an NDTM is variously described as having a "splitting" property
  wherein it can duplicate and fork into children, so to speak, whereas on
  the other hand, it can "guess" the right answer.  Are Garey and Johnson
  responsible for this split in characterization, so that the latter arose
  as a branch of the former from their nonstandard creation?



ld231782@longs.LANCE.ColoState.EDU