<p>The notation $m^{O(1)}$  just denotes the set of functions of polynomial growth rate, so that would be indeed confusing. The class of functions computable in polynomial time is usually denoted $\mathsf{FP}$.</p>

CC BY-SA 3.0
2012-11-13T13:56:50.827Z
2012-11-13T13:56:50.827Z
Jan Johannsen
<p>I write paper and I want to distinguish between the class of decision problems which can be decided in polynomial time and the class functions which can be computed in polynomial time. 
The first is just written as $\mathrm{P}$ or $\mathrm{PTIME}$, right? Can the latter be denoted as $m^{\mathcal{O}(1)}$ or is this a confusing definition?</p>

CC BY-SA 3.0
2012-11-12T17:11:14.113Z
$m^{O(1)}$ just denotes functions of polynomial growth rate, so that would be indeed confusing. The class you are looking for us usually denoted $\mathsf{FP}$.
Jan Johannsen
CC BY-SA 3.0
2012-11-12T19:07:20.743Z
@JanJohannsen maybe make this an answer ?
Suresh Venkat
CC BY-SA 3.0
2012-11-14T08:01:01.917Z
I guess this is more fitting for http://cs.stackexchange.com/
funkstar
<cc.complexity-theory><terminology>
Set of functions computable in polynomial time
Joachim
# Set of functions computable in polynomial time

(Asked by: username_0 on 2012-11-12)

I write paper and I want to distinguish between the class of decision problems which can be decided in polynomial time and the class functions which can be computed in polynomial time.
The first is just written as $\mathrm{P}$ or $\mathrm{PTIME}$, right? Can the latter be denoted as $m^{\mathcal{O}(1)}$ or is this a confusing definition?

**Tags:** cc.complexity-theory, terminology

> **Comments:**
> **username_1**: $m^{O(1)}$ just denotes functions of polynomial growth rate, so that would be indeed confusing. The class you are looking for us usually denoted $\mathsf{FP}$.  
> **username_2**: @JanJohannsen maybe make this an answer ?  
> **username_3**: I guess this is more fitting for http://cs.stackexchange.com/  

---

## 1 answers

### Answer by username_1 on 2012-11-13. Score: 8 | Accepted answer

The notation $m^{O(1)}$ just denotes the set of functions of polynomial growth rate, so that would be indeed confusing. The class of functions computable in polynomial time is usually denoted $\mathsf{FP}$.


---

