I am searching for statements of the above form, that is, asserting the existence of a finite set $F$ of languages and one or more operations $\otimes\colon \mathcal{P}(\Sigma^*) \times \mathcal{P}(\Sigma^*) \to \mathcal{P}(\Sigma^*)$ such that $\mathsf{P}$ is the smallest class containing $F$ and closed under $\otimes$.

Ideally, the operations should be computable and natural in some intuitive sense, and the languages in $F$ quite simple. I'd like to avoid, say, that a language of $F$ encodes all polytime machines, or that one operation "runs" a Turing machine.

  • 1
    $\begingroup$ The descriptive complexity characterization of $\mathsf{P}$ as $(\mathsf{FO} + \mathsf{LFP})$, while not formally what you're asking for, has a similar flavor. $\endgroup$ – Andrew Morgan Jul 7 '16 at 12:45
  • 1
    $\begingroup$ @AndrewMorgan: Thanks! I do know this characterization, and other similar ones, but indeed, my statement is quite restrictive—and on purpose so! While working on language-theoretical frameworks expressing descriptive complexity classes, I ended up with a statement of the question's form, hence I'm wondering if there are others to compare it to. Cheers! $\endgroup$ – Michaël Cadilhac Jul 7 '16 at 13:48
  • 1
    $\begingroup$ You probably are aware of the characterizations of the function class $\mathsf{FP}$ of this form, are you? $\endgroup$ – Jan Johannsen Jul 7 '16 at 14:54
  • 1
    $\begingroup$ Bellantoni and Cook, a new recursion-theoretic characterization of the polytime functions, 1992. $\endgroup$ – Kaveh Jul 8 '16 at 0:37
  • 1
    $\begingroup$ Leivant, Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time, 1995. $\endgroup$ – Kaveh Jul 8 '16 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.