Skip to main content
fixed typo
Source Link
Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366

As @Robert Israel points out, the linear case is MUCH easier than the general case, and the really general case (arbitrary inequalities of the form $f(\mathbf{x}) \geq 0$) is clearly undecidable, but if the inequalities are polynomial, this is the problem of "quantifier elimination over real closed fields", which you can google. The first algorithm was "Tarski's algorithm", there have been many improvements since, most of them used by computer algebra systems (Mathematica, Maple, etc).

As @Robert Israel points out, the linear case is MUCH easier than the general case, and the really general case (arbitrary inequalities of the form $f(\mathbf{x}) \geq 0$ is clearly undecidable, but if the inequalities are polynomial, this is the problem of "quantifier elimination over real closed fields", which you can google. The first algorithm was "Tarski's algorithm", there have been many improvements since, most of them used by computer algebra systems (Mathematica, Maple, etc).

As @Robert Israel points out, the linear case is MUCH easier than the general case, and the really general case (arbitrary inequalities of the form $f(\mathbf{x}) \geq 0$) is clearly undecidable, but if the inequalities are polynomial, this is the problem of "quantifier elimination over real closed fields", which you can google. The first algorithm was "Tarski's algorithm", there have been many improvements since, most of them used by computer algebra systems (Mathematica, Maple, etc).

Source Link
Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366

As @Robert Israel points out, the linear case is MUCH easier than the general case, and the really general case (arbitrary inequalities of the form $f(\mathbf{x}) \geq 0$ is clearly undecidable, but if the inequalities are polynomial, this is the problem of "quantifier elimination over real closed fields", which you can google. The first algorithm was "Tarski's algorithm", there have been many improvements since, most of them used by computer algebra systems (Mathematica, Maple, etc).