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'?
What's the meaning of the name P/poly?
terminology;complexity classes
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$.