Observation of implicit complexity by non confluence

guillaume(dot)bonfante(at)loria(dot)fr We propose to consider non confluence with respect to implicit complexity. We come back to some well known classes of first-order functional program, for which we have a characterization of their intentional properties, namely the class of cons-free programs, the class of programs with an inter-pretation, and the class of programs with a quasi-interpretation together with a termination proof by the product path ordering. They all correspond to PTIME. We prove that adding non confluence to the rules leads to respectively PTIME, NPTIME and PSPACE. Our thesis is that the separation of the classes is actually a witness of the intentional properties of the initial classes of programs. In implicit complexity theory, one of the issues is to characterize large classes of programs, not extensionally but intentionally. That is, for a given class of functions, to delineate the largest set of programs computing this class. One of the issues with this problem is that it is hard to compare (classes of) programs. Indeed, strict syntactical equality is definitely too restrictive, but larger (the interesting ones) relations are undecidable. So, comparing theories (defining their own class of programs) is rather complicated. Usually, one gives a remarkable example, illustrating the power of the theory. We propose here an other way to compare sets of programs. The idea is to add a new feature–i