My Favourite Problems

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

Definability of Zariski-closed sets

A subset X of the n-dimensional euclidean space is closed if and only for every point which is not in X,
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:

  • O. Chapuis and P. Koiran. Definability of geometric properties in algebraically closed fields.
    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.

  • P. Koiran. On defining irreducibility. preprint, 1999.

    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.

    Stability of saturated linear systems

    A satuarated linear system is an iterated map dynamical system with state space the n-dimensional box [-1,1]^n.
    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 ?

    Iterated maps on the interval

    Let F be a piecewise-linear map on the unit interval and x a point in this interval.
    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:

  • P. Koiran and C. Moore. Closed-form analytic maps in one and two dimensions can simulate Turing machines. DIMACS Technical Report 96-25. Theoretical Computer Science, 210(1):217-223, 1999.

  • P. Koiran, M. Cosnard, and M. Garzon. Computability with low-dimensional dynamical systems. Theoretical Computer Science, 132:113-128, 1994.

    It is an open problem whether the following publication is relevant.

  • P. Koiran. A family of universal recurrent networks. Theoretical Computer Science, 168(2):473-480, 1996.

    Systems of algebraic equations

    What is the complexity of deciding the satisfiability of a system of algebraic equations
    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:

  • P. Koiran. Hilbert's Nullstellensatz is in the polynomial hierarchy. Journal of Complexity, 12(4):273-286, 1996. There is a longer paper ( DIMACS Technical Report 96-27) and an erratum.

    Algebraic decision trees

    Let PAR be the class of problems that can be solved in parallel polynomial time over the reals.
    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

  • H. Fournier and P. Koiran. Are lower bounds easier over the reals ?
    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

  • P. Koiran. Computing over the reals with addition and order. Theoretical Computer Science, 133(1):35-48, 1994. LIP Research Report 93-25.

    that the Knapsack problem cannot be solved by polynomial depth decision trees.
    Is this also true in the field of complex numbers ?

    Saturation in the theory of computation over the reals

    Christian Michaux has introduced the class P/const in the theory of computation over the reals. Roughly speaking, a problem is in P/const if it can be solved in polynomial time with a constant amount of advice. Moreover, the advice for inputs of size n must also work for all inputs of size
    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:

  • O. Chapuis and P. Koiran. Saturation and stability in the theory of computation over the reals. Technical Report 1997/3, Institut Girard Desargues, Université Claude Bernard Lyon I, 1997.

    VC dimension of arithmetic circuits

    What is the Vapnik-Chervonenkis dimension of circuits made of linear and equality gates?
    This is basically the only gap left in the classification given in:

  • P. Koiran and E. D. Sontag. Neural networks with quadratic VC dimension. Journal of Computer and System Sciences, 54:190-198, 1997. Preliminary version in Advances in Neural Information Processing Systems 8 (NIPS'95), MIT Press, 1996. NeuroCOLT Technical Report 95-44.

    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.

    Back to Pascal Koiran's home page