What is the correct definition of coNP/poly? Complexity Zoo defines coNP/poly as
Complement of NP/poly
Thanks to Emil, I understand it as
&quot;the class of decision problems whose complement can be solved in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function.&quot;
(A polynomial-bounded advice function is a function $f$ that maps each positive integer $n$ to an advice string $f(n)$ of length polynomial in $n$. To be clear, the advice string depends only on $n$; it is independent of the input to the Turing machine.)
I don't clearly understand this definition. A decision problem is basically a yes/no question, and I suppose &quot;solving a decision problem&quot; means answering the yes/no question correctly. But, if that is the case, then solving a decision problem is same as solving the complement of the problem. So, I wonder
What is the meaning of the word 'solve' in the definition of coNP/poly (or NP/poly)?
I am also interested in whether we can define coNP/poly (or NP/poly) in terms of deterministic polynomial time verifiers (as in the definition of NP). The best I could come up with are the following.
NP/poly is the class of decision problems whose yes certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.
coNP/poly is the class of decision problems whose no certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.
Are these definitions correct?
Disclaimer: I have asked a related question in cstheory.stackexchange. At the time of asking that question, I did not know that the problem is in my understanding of the definition. They recommended that I ask the question here. (I shall delete my other question if the only problem is my understanding of the definition).
Thank you
Recall that a decision problem is a language $L \subseteq \{0,1\}^*$.  (This is the language of all words $w$ such that the answer to the yes/no question is &quot;yes&quot;.)
In this context, a Turing machine solves a decision problem $L$ if $L$ is the language accepted by that Turing machine.  In other words, when run on input $w$, the Turing machine halts and accepts if $w \in L$, and halts and rejects if $w \notin L$.