Consider the following image:
The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$.
I know that to prove that it is $NP-hard$, I must reduce a $NPC$ problem to it.
However, I guess that the problem is not $NP$, right? For example, even if we have a "Yes" answer for the items above, how can we fit the small rectangles into the big rectangle in polynomial time?
For the above problem, the answer can includes the placement of small rectangles in the bigger rectangle. So, verifying it is easy, and the problem is $NP$.
Suppose, the question was: is there any subset of rectangles that cover the bigger rectangle so no two rectangles overlap and no gap opens up?
Then, what would be the shape of a certificate? Would it be verifiable in polynomial time? Would it be just a subset of items, or their placements too?
What if it was an optimization problem requesting a subset of items that cover the largest area of the bigger rectangle? Then, we had to check other answers to see that the certificate is the optimum one, and that would make the problem non-NP, right?
How a certificate is defined in such cases, and what is its role in categorizing a problem as $NP$ or non-$NP$?!