Counting classes with finite acceptance types

Abstract

Perfectionnement de la hierarchie de Hausdorff generee par NP. Les nouvelles classes permettent une exacte classification de la complexite de certains problemes de denombrement. Les classes sont caracterisees en termes de machines de Turing polynomiales non deterministes