Skip to main content

Questions tagged [np-intermediate]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
135 views

Is this an example of a natural, strictly NP-intermediate language (assuming EXP ≠ NEXP)?

In the wikipedia page for the NP-intermediate complexity class, the following observation is made: Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this ...
1 vote
1 answer
53 views

Do all P problems reduce to all NPI problems?

It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in ...
3 votes
0 answers
21 views

Is there a comprehensive list of complexity theoretic reductions from and to prime number factorization?

I am interested in the complexity theoretic equivalences of prime number factorization. My interest stems from prime number factorization being one of the few candidates for NPI. I am especially ...
-1 votes
3 answers
122 views

The most subtle NP-"intermediate" problem

What is the $NP$ problem whose status in $P$ or $NP$-complete is still unsettled, as of 2018? This question is inspired by the following two recent breakthroughs: The work of Mulzer et. al on $NP$-...
1 vote
0 answers
32 views

Are there any "natural problems" which are known to be NPI under weak assumptions

Are there any "natural problems" which are known to be NPI under weak assumptions. By weak assumptions I mean something like $P \neq NP$ or $NP \neq Co-NP$
3 votes
0 answers
191 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 ...
1 vote
1 answer
105 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{...
3 votes
1 answer
89 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 ...
16 votes
1 answer
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 ...
1 vote
1 answer
146 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
1 answer
606 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
1 answer
162 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 ...