Warning: this page was last updated in the 20th century.

there is an open ball around this point which does not intersect X.

The property "X is closed" can therefore be expressed by a fisrst-order formula in the language (R,+,-,*,<,I_n) where I_n is a n-ary predicate interpreted by membership to X.

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:

LIP Research Report 98-32. To appear in Mathematical Logic Quarterly.

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.

Let x(t) be the state vector at time t. We first apply a fixed linear transformation A to x(t).

The state vector at time t+1 is then obtained from y(t)=A.x(t) by truncating all components of y(t)

which are smaller than -1 or bigger than 1 to -1 and 1, respectively.

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 ?

We consider the sequence of iterates starting from x: x, F(x), F(F(x)), and so on.

Given F and x, is it decidable whether this sequence reaches a fixed point of F ?

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.

in an algebraically closed field of positive characteristic?

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:

The emptiness problem for semi-algebraic sets, and many other natural geometric problems

are known to be in PAR.

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

LIP Research Report 97-38.

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 ?

less than n.

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:

This is basically the only gap left in the classification given in:

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.