0
$\begingroup$

Consider the following image:

enter image description here

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$?!

$\endgroup$
2
$\begingroup$

The only result that I am aware of (assuming your problem is computable) is the time hierarchy theorem, which implies that $NP\neq NEXPTIME$. If you have a problem that is $NEXPTIME$-hard and show that that problem reduces to your problem, you've shown your problem isn't in $NP$. Since $NEXPTIME\subseteq EXPSPACE$, an $EXPSPACE$-hard problem would work as well.

Your problem is in $NP$, however.

$\endgroup$
  • $\begingroup$ Thank you! you may look at my update too... $\endgroup$ – Ahmad Nov 8 '18 at 17:33
  • 1
    $\begingroup$ @Ahmad the same certificate would apply for positive cases. $\endgroup$ – Stella Biderman Nov 8 '18 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.