Timeline for A fast way to decide satisfiability of a set of simple fewnomial inequalities?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2011 at 12:55 | comment | added | Josephine | @Thierry Zell: As i understand Khovanskii's Bound, it only requires that the number $n$ of variables and the number $k$ of distinct monomials in the system of polynomials grow at most linear with the number of polynomials in the system. Is that correct? | |
| Oct 21, 2011 at 11:40 | vote | accept | Josephine | ||
| Oct 20, 2011 at 13:50 | comment | added | Thierry Zell | Well, if you consider dense polynomials, say homogeneous of degree d in n variables, then the number of monomials is n+d-1 choose n-1. So it grows polynomially with the degree. The idea behind fewnomials (due to Khovanskii) is to look instead at a fixed number of monomials, but for which the degrees are unknown (i.e. can be arbitrarily large). SO for instance $x^N+x+1$ would be a fewnomial, and indeed, the number of real roots of this polynomial is 0 or 1, whatever the value of $N$ may be. | |
| Oct 20, 2011 at 13:39 | history | edited | Josephine | CC BY-SA 3.0 |
Considered NP-hardness.
|
| Oct 20, 2011 at 13:36 | comment | added | Josephine | @Thierry Zell: Interesting. I was not able to find a definition of the term fewnomial. All i could find, was theorems that state that the number of nondegenerate roots of a polynomial does not depend on the degree of the polynomial. I don't understand the definition you give above. How can the number of monomials of a polynomial be dependent on the degree of the polynomial? | |
| Oct 20, 2011 at 0:45 | answer | added | Joseph O'Rourke | timeline score: 5 | |
| Oct 19, 2011 at 15:38 | comment | added | Thierry Zell | I expect that there is a polynomial-time (polynomial number of real arithmetic operations) algorithms to do this, but I don't really have time to dot all the i's and cross all the t's right now. But what I have in mind is not easily implemented or available as a black-box, so it depends on if you actually want to use such an algorithm, or simply know it exists. | |
| Oct 19, 2011 at 15:32 | comment | added | Gerhard Paseman | It looks like you have it already: compute differences, take dot products, pay attention to signs. Unless the constraints fit some pattern like disjoint triples, I don't see any nonobvious parallelization or other optimizations. Gerhard "Ask Me About System Design" Paseman, 2011.10.19 | |
| Oct 19, 2011 at 15:09 | comment | added | Thierry Zell | You are misusing the term "fewnomial" here: fewnomials refer to polynomials which have arbitrarily high degree, but the number of monomials is independent on that degree. Here, you have only degree 2... | |
| Oct 19, 2011 at 14:30 | history | edited | Josephine |
added tags
|
|
| Oct 19, 2011 at 12:02 | comment | added | Josephine | I'm unsure how to tag this. Glad for any advice. | |
| Oct 19, 2011 at 12:01 | history | asked | Josephine | CC BY-SA 3.0 |