# 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
"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."

(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 "solving a decision problem" 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

• Do you understand the definition of NP/poly? Do you know what "solve" means in that context? If not, then you should make sure you understand that first before trying to tackle coNP/poly. If yes, then you already know the answer to your question -- it means the same thing.
– D.W.
Dec 4 '20 at 6:51
• @D.W. I don't. I have modified the question to be more clear. Dec 4 '20 at 7:21

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 "yes".)
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$$.
• Thanks for the answer. I have a doubt though. If $w\notin L$, the Turing machine need not halt, right? If the TM could probably not halt on no instances, then it doesn't solve the complement problem automatically (and hence solving a problem is different from solving the complement of the problem). Dec 4 '20 at 10:05