0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Dec 4, 2020 at 6:51
  • $\begingroup$ @D.W. I don't. I have modified the question to be more clear. $\endgroup$
    – Cyriac Antony
    Commented Dec 4, 2020 at 7:21

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Cyriac Antony
    Commented Dec 4, 2020 at 10:05
  • $\begingroup$ @CyriacAntony, I recommend that you get a good textbook on formal languages, as these are pretty basic questions that should be covered there. See also en.wikipedia.org/wiki/Recursive_language#Definitions. $\endgroup$
    – D.W. ♦
    Commented Dec 4, 2020 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.