Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [np-intermediate]

The tag has no usage guidance.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
ckrk's user avatar
  • 131
3 votes
0 answers
189 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 ...
wazdra's user avatar
  • 362
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$
blademan9999's user avatar