There is a significant gap between the Omega(w log w) lower bound and the O(w^2) upper bound. Here w is the number of "programmable parameters".
If equality gates are replaced by sign gates there is a tight Theta(w^2) bound.
Is there such a formula over the complex numbers ?
More precisely, one would like to have a first-order formula F
in the language (C,+,-,*,=,I_n)
such that for any definable (i.e., constructible) subset
of the n-dimensional complex space,
X is closed iff F is true when I_n is interpreted by membership to X.
A relevant publication:
One may ask many other definability questions. For instance,
it is possible to show that for real algebraic varieties,
irreducibility is not definable.
Is this also true for complex algebraic varieties ?
NEW RESULT: both questions have just been solved in a joint paper with Chapuis, Hrushovski and Poizat.
I have a shown in a paper
with Vincent Blondel, Olivier Bournez
and John Tsitsiklis that stability
(more precisely, "global asymptotic stability") of saturated
linear systems is undecidable.
This answers a question of Eduardo Sontag.
Several related properties (global convergence, mortality and nilpotence)
are also undecidable.
Our work raises a number of new questions, however.
For instance, is stability equivalent to global convergence ?
Is nilpotence equivalent to mortality ?
Are these properties undecidable for systems in fixed dimension ?
Even when F is made of only two linear pieces, I do not have a decision algorithm.
For this problem to make sense, F and x must have a finite description.
We assume here that x is rational,
and that the slopes and breakpoints of F are also rational.
The same problem is known to be undecidable in dimension 2. If piecewise-linear functions are replaced by polynomials, the problem is open in any dimension.
Two relevant publications:
It is an open problem whether the following publication is relevant.
I have shown that in characteristic 0, this problem is in the second
level of the polynomial hierarchy
(it is in fact in AM, the "Arthur-Merlin" class)
if one believes in the Generalized Riemann Hypothesis.
In positive characteristic, there is quite a large gap between
the known upper bound (PSPACE) and lower bound (NP).
One could for instance try to put this problem in the polynomial
hierarchy, or prove that is is PSPACE-hard.
In the language of mathematical logic, deciding whether a system is
satisfiable amounts to deciding an "existential formula".
One can also consider formulas with several blocks of quantifiers.
Even if there are only two blocks, it is not known whether the
decision problem in characteristic 0 is in the polynomial hierarchy.
One relevant publication:
Can any problem in PAR be solved by algebraic decision trees of polynomial depth ?
I suggest that the answer might be positive. It would already be interesting to answer this question for specific problems in PAR, e.g., for the linear programming feasibility problem.
Perhaps surprisingly, the corresponding problem
in the model of computation with addition and order only
has a positive answer.
This was proved (in a slightly different language)
by Meyer auf der Heide [Fast algorithms for n-dimensional
restrictions of hard problems.
JACM, 35(3):740--747, 1988]
and Meiser [Point location in arrangements of hyperplanes,
Information and Computation 106(1993), pp 286-303].
Some consequences of these results are discussed in
Note that in the model with addition and equality only, the corresponding problem now has a negative answer. Indeed, it is shown in
that the Knapsack problem cannot be solved by
polynomial depth decision trees.
Is this also true in the field of complex numbers ?
The big question is whether P=P/const.
If this is true a transfer theorem for the problem P=NP would follow: P=NP over the reals if and only if P=NP over any real-closed field containing the reals.
It is easily seen that P=P/const over the complex numbers (this is due to the omega-saturation of C). A similar transfer theorem then follows.
One relevant publication:
There is a significant gap between the Omega(w log w) lower bound and the O(w^2) upper bound. Here w is the number of "programmable parameters".
If equality gates are replaced by sign gates there is a tight Theta(w^2) bound.
