Asked By : akroy
Answered By : Luke Mathieson
We are mainly interested in $poly$, the collection of all polynomially-bounded functions… (p. 192)
Of course they don’t give the reasons for choosing that name, so on the speculative part! Firstly, it should be clear that $P$ and $poly$, although both derived most immediately from the word polynomial, have rather distinct meanings. $P$ as a name refers to deterministic polynomial time, and as a class is the set of all problems solvable in such. $poly$ however is a bound on the advice function, not a time-complexity statement. This is where I speculate that the difference in names stems from; $P$ and $poly$ are quite separate concepts and it would only serve to confuse if we were to write $P/P$ – this notation would suggest some idea of $bigcup_{k} DTIME[n^{k}]/bigcup_{k} DTIME[n^{k}]$, which is certainly an incorrect impression to gives, whereas $P/poly$ immediately suggest $P$ which has something polynomial attached to it but is different to $P$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37502 Ask a Question Download Related Notes/Documents