# Proof of coNE ⊆ NE/poly

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.

• 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$. Apr 12 at 9:16
• 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 Apr 12 at 15:10
• Awesome, thanks! Apr 12 at 15:24
• 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.
– Community Bot
Apr 13 at 11:16