Skip to main content
Share Your Experience: Take the 2024 Developer Survey
6 votes

If coNP ⊆ NP, does that mean coNP = NP?

Yes. Assume co-NP ⊆ NP. Take any NP problem. Its complement is co-NP, therefore NP by co-NP ⊆ NP, so the problem itself is co-NP, QED.
Jean Abou Samra's user avatar
2 votes

Does NSPACE($n^2$) $=$ DSPACE($n^4$)?

I believe this is unknown. There are a couple of barriers: First, it is unknown whether Savitch's theorem is optimal. Imagine we could improve the theorem to show $$\text{NSPACE}(f(n)) \subseteq \text{...
Benjamin Kuykendall's user avatar
1 vote

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

After mulling this over for a long time, I've convinced myself that there is no optimal lookup complexity when insertion complexity is limited to $\mathcal O(\log\log n)$. I've written up my reasoning ...
Franklin Pezzuti Dyer's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible