I'm currently learning about complexity classes and I have a few general questions:

Assume $A, B \in \mathcal{NP}\setminus{\mathcal{P}}, \ A, B \not\in \mathcal{NP-C}$

  • are people generally interested in whether problem $A$ is irreducible (in polynomial time) to problem $B$?
  • if this is generally of interest, how many proofs of this sort have been published and what are the keywords to look for them?
  • can you say that it is, in general, rather easy or rather hard to prove that a problem is not reducible to a problem of about the same difficulty?

I would be very glad if someone would give their insight on this and could direct me to any resources for further learning.

Also, if the notation in the head of this question is formally incorrect, it would be nice if you could correct me (seriously).


migrated from cstheory.stackexchange.com Dec 18 '18 at 7:24

This question came from our site for theoretical computer scientists and researchers in related fields.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.