home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18808 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  2.0 KB
  1. Path: sparky!uunet!math.fu-berlin.de!news.th-darmstadt.de!kirmes!giesl
  2. From: giesl@kirmes.intellektik.informatik.th-darmstadt.de (Juergen Giesl)
  3. Newsgroups: sci.math
  4. Subject: Algorithm for Polynomial Inequalities?
  5. Date: 27 Jan 1993 15:55:02 GMT
  6. Organization: Technical University Darmstadt
  7. Lines: 50
  8. Sender: giesl@kirmes (Juergen Giesl)
  9. Distribution: world
  10. Message-ID: <1k6b8mINNg4u@rs2.hrz.th-darmstadt.de>
  11. NNTP-Posting-Host: kirmes.inferenzsysteme.informatik.th-darmstadt.de
  12. Keywords: Polynomial Inequalities
  13.  
  14.  
  15. A POLYNOMIAL INEQUATION over the natural numbers
  16. is a formula of the following type:
  17.  
  18. FOR ALL natural numbers n1,..,nk: p(n1,...,nk) > 0,
  19.  
  20. where p is a multivariate polynomial of any degree 
  21. with variable coefficients p0,...,pj. 
  22.  
  23.  
  24. A mapping from {po,...,pj} to the natural numbers is a 
  25. SOLUTION to the above inequation, if substituting each pi 
  26. by the number it is mapped to makes the inequation true. 
  27.  
  28.  
  29. A polynomial equation and its solutions are defined analogously. 
  30.  
  31.  
  32. A solution to a set of polynomial inequations and equations 
  33. is a mapping from all occurring variable coefficients to the
  34. natural numbers, which solves each inequation and each equation
  35. in the set.
  36.  
  37.   _______________________________________________________
  38.  | I am searching for an algorithm working as follows:   |
  39.  | Given a set of polynomial inequations and equations   | 
  40.  | over natural numbers,                                 |
  41.  | it returns "solvable" or "don't know".                |
  42.  | If it returns "solvable" then there exists a solution |
  43.  | to the set of inequations and equations.              |
  44.   -------------------------------------------------------
  45.  
  46.  
  47. Due to Lankford the problem of deciding inequalities between
  48. n polynomials over the natural numbers is undecidable. (Although
  49. it is decidable over the real numbers).
  50.  
  51.  
  52. So if anybody knows where to find an algorithm which is able to find
  53. a solution for a reasonably big class of these problems, please
  54. tell me.
  55.  
  56.  
  57. Thank you,
  58.  
  59. Juergen Giesl.
  60.  
  61.  
  62.  
  63.  
  64.