8

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(f)$?

It's easy to show that $\cc{NP} \cap \cc{coNP} \neq \cc{NEXP} \cap \cc{coNEXP}$, at least. Proof: Assume not. Then $$\cc{NEXP} \cap \cc{coNEXP} \subseteq \cc{NP} \cap \cc{coNP} \subseteq \cc{NP} \cup \cc{coNP} \subseteq \cc{NEXP} \cap \cc{coNEXP},$$ so $\cc{NP} = \cc{coNP}$, and hence (by padding) $\cc{NEXP} = \cc{coNEXP}$. But then our assumption implies that $\cc{NP} = \cc{NEXP}$, contradicting the nondeterministic time hierarchy theorem. QED.

But I don't even see how to separate $\cc{NP} \cap \cc{coNP}$ from $\cc{NSUBEXP} \cap \cc{coNSUBEXP}$, as diagonalization seems tricky in this setting.

Jan Johannsen
  • 4,630
  • 2
  • 33
  • 50
William Hoza
  • 1,733
  • 11
  • 23

1 Answers1

1

(This would've been a comment, but it doesn't render properly when I try that.)

"I don't even see how to separate" $\;\;\;$$\mathbf{U}$$\mathbf{q}$$\mathbf{uasiLIN}$ $\cap \; \mathbf{coUquasiLIN} \;\;\;$ from
$[$the linear-exponent version of QIP[2]$] \;\; \cap \;\; [$the linear-exponent version of coQIP[2]$] \;\;\;\;\;$.