Complexité descriptive dans le zoo

Dans mon domaine, si on a pas une super mémoire il existe un Zoo, où l'on peut aller admirer tout un tas de classes de complexité et où des zoologiste ont bien expliqué comment tout ce petit monde se comporte dans la nature.

Cependant, pour des raisons obscures, toute une famille était oublié, et c'est celle sur laquelle je travaille actuellement ! Je viens donc d'offrir au zoo une description de chacune de ses classes, tout du moins de celles que je connais moi même.

Si des gens sont curieux de savoir ce que je fais actuellement, cela concerne beaucoup les classes logiques (si vous savez ce que signifient (et, ou, non, implique, pour tout et il existe, vous êtes bien parti) et les rapport avec la complexité (si vous savez ce qu'est la mesure du temps/de l'espace d'un algorithme c'est mieux), il y a donc à la base le premier ordre FO (suivie de toutes les classes du nom FO(...), ensuite il y a le second ordre SO (avec encore une fois ces variantes et restrictions).

Sans aucun rapport avec la logique, il y a aussi une rapide description du langage de programmation WHILE qui avec certaines restriction décrit tout langages en temps polynomiale/espace logarithmique (avec le petit coté marrant que un programme WHILE ne prendra jamais un temps polynomiale mais peut TOUJOURS se transformer en un tel programme dans un autre langage)

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

La discussion continue ailleurs

URL de rétrolien : http://www.milchior.fr/blog/index.php?trackback/293

Fil des commentaires de ce billet