Consider the following problem, called BoxDepth:

Given a set of $n$ axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?

Say we proved these two statements:

  1. There is a a polynomial-time reduction from BoxDepth to MaxClique.

  2. There is a polynomial-time algorithm for BoxDepth with $O(n^3)$ runtime.

Why don’t these two results imply that P=NP?

  • $\begingroup$ Well, suppose there are $k'$ intersecting rectangles: what structure does that imply in the graph? Suppose there's a $k$-clique in the graph: what structure does that imply in the rectangles? $\endgroup$ – David Richerby Nov 14 '16 at 8:16
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question; you can not "prove a reduction". Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 14 '16 at 17:13
  • $\begingroup$ Please ask only one question per post. Since you already got an answer for c, I'm going to remove the others; feel free to repost them (one at a time). $\endgroup$ – Raphael Nov 14 '16 at 17:13
  • $\begingroup$ You'll note that the new, better title pretty much answers the question. $\endgroup$ – Raphael Nov 14 '16 at 17:15

Part 1 shows how to solve BoxDepth using MaxClique.

Part 2 shows how to solve BoxDepth directly.

None of the parts says anything about solving MaxClique.

| cite | improve this answer | |

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.