home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2384 < prev    next >
Encoding:
Text File  |  1992-11-10  |  1.1 KB  |  33 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!umn.edu!umeecs!quip.eecs.umich.edu!jordans
  3. From: jordans@quip.eecs.umich.edu (Jordan Stojanovski)
  4. Subject: Re: Is the following problem in NP?
  5. Message-ID: <1992Nov10.092835.10526@zip.eecs.umich.edu>
  6. Keywords: NP, polynomials, equations, solvability
  7. Sender: news@zip.eecs.umich.edu (Mr. News)
  8. Organization: University of Michigan EECS Dept., Ann Arbor
  9. References: <1992Nov10.084511.27971@CSD-NewsHost.Stanford.EDU>
  10. Date: Tue, 10 Nov 1992 09:28:35 GMT
  11. Lines: 20
  12.  
  13. In article <1992Nov10.084511.27971@CSD-NewsHost.Stanford.EDU> kolount@cauchy.stanford.edu (Mihail N Kolountzakis) writes:
  14. >
  15. >INPUT: a polynomial F(x_1, ... , x_N) of bounded degree (say 10)
  16. >and integer coefficients (also bounded by say 100).
  17. >
  18. >OUTPUT: YES iff there are _real_ numbers x_1, ... , x_N that satisfy F=0.
  19. >
  20. >Please reply to "kolount@cauchy.stanford.edu".
  21. >
  22. >Mike Kolountzakis
  23. >
  24. >
  25. >
  26. >
  27.  
  28. Yes: Since there is a finite number of polynomials of bounded degree with
  29. bounded integer coefficients, the solution is a table lookup, and your
  30. problem can be solved by a finite automaton.
  31.  
  32. Jordan Stojanovski
  33.