Questions tagged [np-intermediate]
The np-intermediate tag has no summary.
14 questions
2
votes
0
answers
89
views
Does my understanding violate anything known about NP-intermediate classes and crypto?
I've been sort of thinking about $C^{poly}$ witnesses for a certain reason for several years and sort of weaker senses of reductions of problems in the back of my mind, but I just recently saw results ...
- 53
3
votes
0
answers
59
views
Is there a notion similar to NP-intermediate, but for higher classes in PH?
It is well-known that (assuming P$\neq$NP), there are problems in NP that are not NP-hard neither in P. Such class of problems are called NP-intermediate (https://en.wikipedia.org/wiki/NP-intermediate)...
- 559
3
votes
1
answer
207
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 ...
- 65
1
vote
1
answer
100
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 ...
- 327
3
votes
0
answers
33
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
vote
0
answers
51
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$
- 376
-1
votes
3
answers
171
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$-...
- 2,313
1
vote
1
answer
144
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{...
user92914
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 ...
- 2,491
3
votes
0
answers
230
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 ...
- 362
3
votes
1
answer
124
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 ...
- 161
1
vote
1
answer
183
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 ...
- 2,957
10
votes
1
answer
692
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 ...
- 1,683
4
votes
1
answer
208
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 ...
- 1,683