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?
$\begingroup$
$\endgroup$
3
-
10$\begingroup$ $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}$. $\endgroup$– Jan JohannsenNov 12, 2012 at 17:11
-
3$\begingroup$ @JanJohannsen maybe make this an answer ? $\endgroup$– Suresh VenkatNov 12, 2012 at 19:07
-
1$\begingroup$ I guess this is more fitting for cs.stackexchange.com $\endgroup$– funkstarNov 14, 2012 at 8:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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}$.
answered Nov 13, 2012 at 13:56