Questions tagged [np-intermediate]
The np-intermediate tag has no usage guidance.
11
questions
1
vote
1
answer
46
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 ...
- 2,713
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 ...
- 131
-1
votes
3
answers
120
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$-...
- 38.6k
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$
- 336
3
votes
0
answers
174
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 ...
CommunityBot
- 1
1
vote
1
answer
96
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{...
- 2,255
3
votes
1
answer
85
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 ...
- 2,255
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 ...
D.W.♦
- 156k
1
vote
1
answer
143
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 ...
CommunityBot
- 1
10
votes
1
answer
581
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 ...
CommunityBot
- 1
4
votes
1
answer
148
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 ...
- 72k