CE48 - Fondements du numérique: informatique, automatique, traitement du signal

Complexity Theory with Discrete Differential/Difference Equations – DIFFERENCE

Submission summary

We propose to revisit classical mathematical logic, computability and complexity theory using discrete ordinary differential equations (dODEs), sometime also called finite differences. We recently demonstrated that dODEs provide a novel and original approach between the classical world of computer science dealing with discrete objects (words, bytes, etc) and the continuous world of classical ordinary differential equations. We propose concretely: to characterize in a machine indepedent way main classes of complexity theory, extend the framework to deal with more general structures and more general equations than ordinary differential equations, relate the approach to classical approaches in logic, and devise applications with respect to the classification of hardness of problems in verification, and of the complexity of models coming from bioinformatics. Included experts come from complexity theory, logic, constraints solving, verification, computera algebra, bioinformatics.

Project coordination

Olivier BOURNEZ (Laboratoire d'Informatique de l'Ecole Polytechnique)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

IMT Institut de Mathématiques de Toulouse
LACL Laboratoire d'Algorithmique, Complexité et Logique
IRIF Institut de Recherche en Informatique Fondamentale
CNRS-LIX Laboratoire d'Informatique de l'Ecole Polytechnique

Help of the ANR 357,061 euros
Beginning and duration of the scientific project: November 2020 - 48 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter