# Proofs of the form “$A, B \in \mathcal{NP}\setminus{\mathcal{P}}, \ A, B \not\in \mathcal{NP-C}, \ A \not\leq_p B$”

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.comDec 18 '18 at 7:24

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