1

I am having difficulty understanding the relationship between the complexity of two classes of problems, say NP-hard and NP-complete problems.

The answer at https://stackoverflow.com/a/1857342/ states:

NP Hard

Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.

The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

If a problem Y can be reduced to X in polynomial time, should we not say that Y is at least as hard as X? If a problem Y is reducible to X in polynomial time, then the time required to solve Y is polynomial time + the time required to solve X. So it appears to me that problem Y is at least as hard as X.

But the quoted text above says just the opposite. It says, if an NP-complete problem Y is reducible to an NP-hard problem X, then the NP-hard problem is at least as hard as the NP-complete problem.

How does this make sense? Where am I making an error in thinking?

Lone Learner
  • 18,088
  • 20
  • 102
  • 200
  • This should be a comment to the original SO answer post, because either its text can be improved, or the text has a clerical error. Either way, an answer here will not improve the already linked SO question and answer, so this question will only cause future visitors to remain equally confused. – Mike 'Pomax' Kamermans Mar 21 '17 at 04:55
  • @Mike'Pomax'Kamermans The text in the original SO answer post is correct. There is no clerical error there. An answer to this question would not improve that answer, but add distraction. This question has a much smaller scope than the linked answer, i.e. understanding the relationship between the time complexity of two problems only, and not necessarily P, NP, NP-complete and NP-hard problems that the linked answer discusses. In fact, it is possible for me to rewrite my entire question without linking to the linked answer, but I thought it is good to include some context around my question. – Lone Learner Mar 21 '17 at 05:02
  • 3
    If Y is reducible to X then if you know how to solve X you know how to solve Y, but if you know how to solve Y you don't necessarily know how to solve X. E.g. let Y be the problem of finding the largest integer whose square is less than t, given t. Then Y is reducible to boolean satisfaction but we know how to solve Y in polynomial time (because we know how to take square roots) but we don't know how to solve SAT in polynomial time. – mcdowella Mar 21 '17 at 05:12
  • @mcdowella The example you provide makes sense. But let me attempt a counterexample. Let Y be the problem of finding the sum of all integers in an n x n x n matrix. It takes O(n^3) time to solve Y. But Y can be reduced to a problem X of finding the sum of all integers in an n x n matrix and solving X n times. It takes only O(n^2) time to solve X. So in this case X is easier than Y, not at least as hard as Y. What is the error in my counterexample? – Lone Learner Mar 21 '17 at 05:21
  • @LoneLearner: In your counterexample Y isn't reduced to X. Instead Y is reduced to Xn and Xn is still O(n^3) – slebetman Mar 21 '17 at 05:23
  • A problem is Z-hard if the **fastest** method to solve it is in Z. Y is **at most** as hard as X. Polynomial reduction time is considered negligible as it doesn't make a priblem any harder (the easiest problems are polynomial). You can solve Y by reducing it to X and solving X, but this says nothing abot the existence of faster methods to solve Y. If there are some, then Y is in fact easier than X. – n. m. could be an AI Mar 21 '17 at 06:02
  • @n.m. "A problem is Z-hard if the fastest method to solve it is in Z." -- Is this equivalent to "A problem p is Z-hard if every problem z in Z is reducible to p"? I know that the latter is a definition of Z-hard. Trying to see how your definition works correctly. Let me an attempt a counterexample to your definition. Let Z = {z1, z2, ...} such that z1 is the fastest method to solve a problem p and z2 is not reducible to p. Now p is Z-hard as per your definition but it is not Z-hard as per mine. What is the error in my counterexample? – Lone Learner Mar 21 '17 at 06:23
  • Sorry I didn't use the standard definition of hardness. My bad, I should have used a different term. The standard definition of hardness talks about the problem space, I'm talking about the solution space. The two are not equivalent at all. For example we don't know for sure if NP-hard (standard definition) problems are exponentially hard (my definition), but strongly suspect that this is the case. Let's use another term, say Z-difficult, OK? – n. m. could be an AI Mar 21 '17 at 07:02

2 Answers2

4

Your error is in supposing that you have to solve X in order to solve Y. Y might be actually much easier, but one way to solve it is to change it to an instance of X problem. And since we are in big O notation and in NP class we are way past linear algorithms, you can always safely discard any linear parts of an algorithm. Heck you can almost safely discard any polynomial parts until P=NP problem is solved. That means O(f(n) + n) = O(f(n)) where n=O(f(n)).

Example (which is obviously with neither NP-hard or NP-complete problems but just a mere illustration): You are to find the lowest number in an unsorted array of n numbers. There is obvious solution to iterate over the whole list and remember the lowest number you found, pretty straight-forward and solid O(n).

Someone else comes and says, ok, let's change it to sorting the array, then we can just take the first number and it will be the lowest. Note here, that this conversion of the problem was O(1), but we can for example pretend there had to be some preprocessing done with the array that would make it O(n). The overall solution is O(n + n*log(n)) = O(n * log(n)).

Here you too changed easy problem to a hard problem, thus proving that the hard problem is indeed the same or harder as the easy one.

Basically what the NP-hard problem difinition means is, that X is at least as hard as an NP-complete Y problem. If you find an NP-complete Y problem that you can solve by solving X problem, it means either that X is as hard or harder than Y and then it is indeed NP-hard, or if it is simpler, it means you found an algorithm to solve Y faster than any algorithm before, potentially even moving it out of NP-complete class.

Another example: let's pretend convolution is in my set of "complete", and normally takes O(n²). Then you come up with Fast Fourier Transformation with O(n * log(n)) and you find out you can solve convolution by transforming it to FFT problem. Now you came up with a solution for convolution, which is o(n²), more specifically O(n * log(n)).

Ordoshsen
  • 650
  • 3
  • 15
0

Let I_X be the indicator function of X (i.e., 1 if the input is in X and 0 otherwise) and I_Y be the indicator function of Y. If Y reduces to X via a function f that can be computed in polynomial-time, then I_Y = I_X . f, where . denotes function composition. X is at least as hard as Y because, given an algorithm for I_X, the formula above gives an algorithm for I_Y that, for any class of running times closed under polynomial substitution (e.g., polynomial, exponential, finite), if the algorithm for I_X belongs to the class, then so does the algorithm for I_Y. The contrapositive of this statement is, if Y has no fast decision procedure, then X has no fast decision procedure.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120