<p>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 <span class="math-container">$c_n= |\{x ∈ {0,1}^n\mid x \notin A\}|$</span>. How will the problem be solved? Will also appreciate any reference paper that explores it further.</p>

CC BY-SA 4.0
2024-04-12T09:16:33.077Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2024-04-12T15:10:48.327Z
I fixed the broken link in the complexity zoo to Fortnow's 2004 blog post. The post you're looking for is here: https://blog.computationalcomplexity.org/2004/01/little-theorem.html
Joshua Grochow
CC BY-SA 4.0
2024-04-12T15:24:21.887Z
Awesome, thanks!
rock_lee
CC BY-SA 4.0
2024-04-13T11:16:48.883Z
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
<cc.complexity-theory>
Proof of coNE ⊆ NE/poly
rock_lee
# Proof of coNE ⊆ NE/poly

(Asked by: username_0 on 2024-04-12)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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$.  
> **username_2**: I fixed the broken link in the complexity zoo to Fortnow's 2004 blog post. The post you're looking for is here: https://blog.computationalcomplexity.org/2004/01/little-theorem.html  
> **username_0**: Awesome, thanks!  
> **username_3**: 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.  

---

## 0 answers

