Lets say Problem A,B are in NP.
Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B
Is there a difference in "hardness" of a Problem even in NP?
Or must Problem B at least be NP-Complete?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
It depends on the problems. Just knowing that $A$ and $B$ are in $NP$ doesn't tell you whether $A$ is reducible to $B$.
If $B$ is in $P$ and $A$ is $NP$-complete, then $A$ cannot be reduced to $B$ (unless $P=NP$).
If $A$ is in $P$ then it can be reduced to any problem $B$ except $\emptyset$ and $\Sigma^*$.
If $B$ is $NP$-complete then any problem (in $NP$) can be reduced to it.
Ladner's theorem tells us that if $A$ is non-trivial, $A <_m B$ and $B$ is in $NP$, then there is some $C$ with $A <_m C <_m B$. Note that $A <_m C$ means that $A$ is polytime many-one reducible to $C$, but not vice versa.
So not only are there different levels of hardness inside $NP$, provided that $P \neq NP$, but these levels are even dense (between any two levels is another level).
Provided that $P \neq NP$, we can also get plenty of incomparable problems inside $NP$.