home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1863 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  1.4 KB
  1. Path: sparky!uunet!spool.mu.edu!uwm.edu!rutgers!netnews.upenn.edu!gradient.cis.upenn.edu
  2. From: freeman@gradient.cis.upenn.edu (Jon Freeman)
  3. Newsgroups: comp.theory
  4. Subject: Two questions about CSP's
  5. Message-ID: <87907@netnews.upenn.edu>
  6. Date: 4 Sep 92 03:04:41 GMT
  7. Sender: news@netnews.upenn.edu
  8. Organization: University of Pennsylvania
  9. Lines: 23
  10. Nntp-Posting-Host: gradient.cis.upenn.edu
  11.  
  12. Greetings.
  13.  
  14. 1.  I would like to obtain a list of references that discuss the time
  15. and space complexity of converting the variables in a constraint
  16. satisfaction problem (CSP) from non-binary to binary form (i.e.,
  17. converting a CSP to a SAT problem).
  18.  
  19. 2.  I would also like some pointers to quotes from the literature in
  20. which researchers express their opinion as to which of these
  21. representations, if any, is better for a particular CSP technique or
  22. set of techniques.  For example, in their paper "Backtracking with
  23. Multi-Level Dynamic Search Rearrangement" (Acta Informatica 15:99-113,
  24. 1981), Purdom, Brown, and Robertson state:
  25.  
  26.     "Transforming a problem into one with binary variables
  27.      gives maximum scope to search rearrangement."
  28.  
  29.             Thanks in advance,
  30.                    Jon
  31. -------------------------------------------------------------------------------
  32. "If the accelerator (gas pedal) sticks, the   | Jon Freeman
  33. car will often keep going faster and faster." | freeman@gradient.cis.upenn.edu
  34.    --Pennsylvania Driver's Manual, p. 55      | Office: (215) 898-4612
  35.