Questions tagged [np-intermediate]
The np-intermediate tag has no usage guidance.
3
questions with no upvoted or accepted answers
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
3
votes
0
answers
173
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
1
vote
0
answers
30
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$
- 338