Questions tagged [np-intermediate]

The tag has no usage guidance.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
1answer
863 views

Complexity class of this problem?

I am trying to understand to which complexity class the following problem belongs: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients ...
9
votes
0answers
243 views

Is the infinitely-often version of Ladner's theorem known?

We say two languages $\;\;\; L\hspace{.02 in},\hspace{-0.02 in}L' \: \subseteq \: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^* \;\;\;$ agree infinitely-often with each other if and ...
9
votes
0answers
256 views

Are there sampNP-intermediate problems?

I approximately copied the brief "introduction" to average-case complexity theory of NP from my previous question. However, this question is completely different, so please read on It is conjectured ...