# Questions tagged [np-intermediate]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
22k views

### Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
4k views

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
2k views

### Techniques for showing that problem is in hardness "limbo"

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
2k views

### Why are so few natural candidates for NP-intermediate status?

It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates ...
2k views

### NP-intermediate problems with efficient quantum solutions

Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) ...
It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\... 7answers 3k views ### Is there a natural problem in quasi-polynomial time, but not in polynomial time? László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ... 1answer 524 views ### Natural candidates for the hierarchy inside NPI Let's assume that$\mathsf{P} \neq \mathsf{NP}$.$\mathsf{NPI}$is the class of problems in$\mathsf{NP}$which are neither in$\mathsf{P}$nor in$\mathsf{NP}$-hard. You can find a list of problems ... 2answers 771 views ### GI-hard graph problem not known to be$NP$-complete Graph Isomorphism ($GI$) is good candidate for$NP$-intermediate problem.$NP$-intermediate problems exist unless$P=NP$. I'm looking for natural problem that is hard for$GI$under Karp reduction (A ... 1answer 1k views ### Are there "NP-Intermediate-Complete" problems? Assume P$\ne$NP. Ladner's Theorem says that there are NP Intermediate problems (problems in NP that are neither in P nor NP-Complete). I have found some veiled references online that suggest (I ... 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 ... 1answer 386 views ### Is$P^{NPI}$different from$P^{NP}$? Can we prove that for every language$L\in\mathsf{NP}$that is not$\mathsf{NP}$-hard (this assumes$\mathsf P \ne \mathsf{NP}$),$\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$? Alternately, can this be ... 3answers 892 views ### Why are NPI problems not all of the same complexity? How does one look at a problem and reason that it is likely NP-Intermediate as opposed to NP-Complete? It is often pretty simple to look at a problem and tell whether it is likely NP-Complete or not ... 3answers 970 views ### Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space? There are some NP-Complete problems ($ \mathsf{SAT} $,$ \mathsf{SUBSETSUM} $, etc.) known to be in$ \mathsf{DSPACE(n)} $. What about the sub-linear spaces? Is there any known NP-Complete (or NP-... 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 ... 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 ... 1answer 202 views ### Is any QMA-intermediate problem known? Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been ... 1answer 73 views ### NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following: There is a value$\...
Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ ...