If a problem is not in NP, prove that every NP problem can be efficiently reduced to it
I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?


No. There is a stupidly simple argument here: the empty language (i.e., a problem with no yes-instances) is in NP, but no problem in P can be reduced to it.


  Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP?


Yes (conditional on some complexity theory assumptions). Let's take some stupidly hard problem $L$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice. Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.