Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
10  
$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 Nov 12 '12 at 17:11
3  
@JanJohannsen maybe make this an answer ? –  Suresh Venkat Nov 12 '12 at 19:07
1  
I guess this is more fitting for cs.stackexchange.com –  funkstar Nov 14 '12 at 8:01

1 Answer 1

up vote 8 down vote accepted

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.