Questions tagged [np-intermediate]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-2
votes
3answers
94 views

The most subtle NP-“intermediate” problem

What is the $NP$ problem which status (in $P$ or $NP$-complete) is still unsettled, as of 2018? This question is inspored by the following two recent breakthroughs: The work of Mulzer et. al on $NP$-...
1
vote
1answer
46 views

Assuming NP≠coNP, do we have a similar theorem to Ladner's?

We have that $\mathrm{NP\neq coNP\iff NP\neq NP\cap coNP}$. So by assuming that $\mathrm{NP\neq coNP}$, can we prove the existence of intermediate problem between $\mathrm{NP}$-complete and $\mathrm{...
15
votes
1answer
1k views

NP-complete problem with a polynomial number of yes-instances?

I have the impression that for every NP-complete problem, for infinitely many input sizes $n$, the number of yes-instances over all possible inputs of size $n$, is (at least) exponential in $n$. Is ...
3
votes
0answers
126 views

Complete problems in NP∩coNP

I often read in Complexity literature that NP∩coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ? By proved, I mean that there would be a theorem that would relate the ...
3
votes
1answer
72 views

Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$

My question is as follows: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$, where $A \leq _T^p B$ if there exists a ...
0
votes
1answer
122 views

Is following observation on Ladner's theorem correct?

Suppose $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds? Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is ...
10
votes
1answer
337 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
4
votes
1answer
97 views

Constructing languages in NPI other than through Ladner's Theorem

I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse ...