Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

Question

I am taking a complexity class now, and I struggle to understand the concept of "hardness":
Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \textsf{coNP}$, $L$ cannot be $\textsf{NP}$-complete. The formal meaning is that not all languages in $\textsf{NP}$ can be reduced to $L$, but does it mean that $L$ is easier to solve than $\textsf{NP}$-complete language (in the sense that it is more likely to have non-exponential algorithm which decides it)?

Is it plausible that the optimal algorithm for $L$ is exponential? (For 3-SAT there is a known assumption, ETH, which as far as I understand states that the optimal algorithm for it has to be exponential).

Answer 1

You had several questions in there, let's just look at a couple of them, the way I understood you.

Is $L \in \textsf{NP} \cap \textsf{coNP}$ "easier" than problems that are $\textsf{NP}$-hard?

Yes, we believe it is (but as gnasher729 points out in a comment, we don't know for sure; $\textsf{NP}$ could still be equal to $\textsf{P}$, in which case the statement is not entirely correct). ("Hardness" means that it is at least as hard as all the problems in the class. "Completeness" means that it is "hard" and is contained in the class in question., see the reference question [1].)

We do believe that $\textsf{NP} \cap \textsf{coNP}$ is strictly contained in $\textsf{NP}$, and that therefore $L$ cannot be $\textsf{NP}$-hard.

Could it be that the optimal algorithm for $L$ is exponential?

That could very well be. Factoring is in $\textsf{NP} \cap \textsf{coNP}$ [2], and we don't believe there exists a polynomial time algorithm for Factoring.

1. What is the definition of P, NP, NP-complete and NP-hard?
2. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp

• gnasher729: We may believe that the intersection of NP and coNP doesn't contain NP-complete languages, but we don't know. Nothing is proven.
• Ainsley H.: I've updated the wording to make it more clear that we don't know if for sure.