I'm finding it hard proving that NE/poly contains coNE which is backed by Complexity Zoo. It states that we can use the proof for NEXP/poly containing coNEXP but the link to the reference paper proving this (folklore result reported in Fortnow's weblog) is broken. I'd assume that to solve the coNE ⊆ NE/poly problem, we can use the advice $c_n= |\{x ∈ {0,1}^n\mid x \notin A\}|$. How will the problem be solved? Will also appreciate any reference paper that explores it further.

  • 1
    $\begingroup$ Yes, take $c_n$ as advice, assuming $A$ is a coNE language you are trying to put in NE/poly. Then to test membership in $A$ in NE with this advice: given $x$ of length $n$, attempt to nondeterministically generate in lexicographic order $c_n$ many strings $w\notin A$ of length $n$ such that $w\ne x$. This succeeds iff $x\in A$. $\endgroup$ Apr 12 at 9:16
  • 1
    $\begingroup$ I fixed the broken link in the complexity zoo to Fortnow's 2004 blog post. The post you're looking for is here: blog.computationalcomplexity.org/2004/01/little-theorem.html $\endgroup$ Apr 12 at 15:10
  • $\begingroup$ Awesome, thanks! $\endgroup$
    – rock_lee
    Apr 12 at 15:24
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Apr 13 at 11:16


Your Answer

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

Browse other questions tagged or ask your own question.