[FOM] Is this known to be undecidable?
joeshipman at aol.com
Sun Dec 31 01:57:05 EST 2006
Given: a multivariable polynomial p(x1,x2,...,x_n,y) and a univariate
polynomial q(z), in the language of fields.
Assume the axioms for fields, and the axioms for characteristic 0 if
Is it decidable whether
Forall (x1,...,xn) Thereexists y p(x1,...,x_n,y)=0
Thereexists z q(z)=0
In other words, if I can solve all equations of type p, can I solve
(If it is undecidable when I generalize to allow more existentially
quantified variables in p and q, that would also be worth knowing, but
I am mainly interested in the specific case of only one existentially
quantified variable, which seems quite difficult enough!)
Check out the new AOL. Most comprehensive set of free safety and
security tools, free access to millions of high-quality videos from
across the web, free AOL Mail and more.
More information about the FOM