home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2386 < prev    next >
Encoding:
Text File  |  1992-11-10  |  1.2 KB  |  28 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!think.com!ames!stanford.edu!CSD-NewsHost.Stanford.EDU!Xenon.Stanford.EDU!robert
  3. From: robert@Xenon.Stanford.EDU (Robert Kennedy)
  4. Subject: Re: Is the following problem in NP?
  5. Message-ID: <robert.721425354@Xenon.Stanford.EDU>
  6. Keywords: NP, polynomials, equations, solvability
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: CS Department, Stanford University, California, USA
  9. References: <1992Nov10.084511.27971@CSD-NewsHost.Stanford.EDU> <1992Nov10.092835.10526@zip.eecs.umich.edu>
  10. Date: 10 Nov 92 19:55:54 GMT
  11. Lines: 15
  12.  
  13. jordans@quip.eecs.umich.edu (Jordan Stojanovski) writes:
  14. >Yes: Since there is a finite number of polynomials of bounded degree with
  15. >bounded integer coefficients, the solution is a table lookup, and your
  16. >problem can be solved by a finite automaton.
  17.  
  18. The polynomial in the input has N variables, where N is the input
  19. size. You have to generate this table "on the fly" once you know N.
  20. Your method is badly exponential. If the polynomial had been
  21. univariate you would have been right.
  22.  
  23.     -- Robert Kennedy
  24.  
  25. Robert Kennedy                    (415) 723-4532 (office)
  26. robert@cs.stanford.edu                (415) 322-7367 (home voice)
  27. Computer Science Dept., Stanford University    (415) 322-7329 (home tty)
  28.