I understand the normal definitions of the P/poly class, but I'm curious how the name came about.
The syntax of the name looks like a quotient group, but I can't think of any way to define P/poly that would use a quotient. Is 'A/B' defined to be something like "the class of problems that would be solvable as efficiently as those in A when given B amounts of advice"?
If the 'poly' in 'P/poly' refers to the polynomial amount of advice, why is it not 'P/P'? That is, why do we have two different abbreviations for 'polynomial'?
Asked By : akroy
Answered By : Luke Mathieson
Your second intuition is correct, the $poly$ refers to the bound on the advice. The first definition of this class (that I can find) is in Karp & Lipton's "Turing Machines that Take Advice" (pdf), and in particular:
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
0 comments:
Post a Comment
Let us know your responses and feedback