<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2016-07-07T12:45:41.567Z
The descriptive complexity characterization of $\mathsf{P}$ as $(\mathsf{FO} + \mathsf{LFP})$, while not formally what you're asking for, has a similar flavor.
Andrew Morgan
CC BY-SA 3.0
2016-07-07T13:48:54.710Z
@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!
Michaël Cadilhac
CC BY-SA 3.0
2016-07-07T14:54:47.403Z
You probably are aware of the characterizations of the function class $\mathsf{FP}$ of this form, are you?
Jan Johannsen
CC BY-SA 3.0
2016-07-07T17:39:42.950Z
@JanJohannsen:  I recall reading such a thing, but I'd appreciate if you'd refresh my failing memory!
Michaël Cadilhac
CC BY-SA 3.0
2016-07-08T00:37:55.480Z
Bellantoni and Cook, [a new recursion-theoretic characterization of the polytime functions](https://www.cs.toronto.edu/~sacook/homepage/ptime.pdf), 1992.
Kaveh
CC BY-SA 3.0
2016-07-08T00:39:28.543Z
Leivant, [Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time](http://doi.org/10.1007/978-1-4612-2566-9_11), 1995.
Kaveh
CC BY-SA 3.0
2016-07-08T08:25:23.323Z
I was thinking of the same characterizations that Kaveh mentioned, and also the classic one by Cobham. I don't have a reference at hand, but you'll find it in the papers linked by Kaveh.
Jan Johannsen
<cc.complexity-theory><polynomial-time>
$\mathsf{P}$ is the closure of [finite set] under [operation between languages]
Michaël Cadilhac
# $\mathsf{P}$ is the closure of [finite set] under [operation between languages]

(Asked by: username_0 on 2016-07-07)

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.

**Tags:** cc.complexity-theory, polynomial-time
> **Comments:**
> **username_1**: The descriptive complexity characterization of $\mathsf{P}$ as $(\mathsf{FO} + \mathsf{LFP})$, while not formally what you're asking for, has a similar flavor.  
> **username_0**: @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!  
> **username_2**: You probably are aware of the characterizations of the function class $\mathsf{FP}$ of this form, are you?  
> **username_0**: @JanJohannsen:  I recall reading such a thing, but I'd appreciate if you'd refresh my failing memory!  
> **username_3**: Bellantoni and Cook, [a new recursion-theoretic characterization of the polytime functions](https://www.cs.toronto.edu/~sacook/homepage/ptime.pdf), 1992.  
> **username_3**: Leivant, [Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time](http://doi.org/10.1007/978-1-4612-2566-9_11), 1995.  
> **username_2**: I was thinking of the same characterizations that Kaveh mentioned, and also the classic one by Cobham. I don't have a reference at hand, but you'll find it in the papers linked by Kaveh.  

---

## 0 answers

