Skip to main content
Tweeted twitter.com/StackCSTheory/status/1227110182443982848
Bounty Ended with Jeffε's answer chosen by Robin Kothari
Bounty Started worth 50 reputation by Robin Kothari
updated question; improved formatting
Source Link
Robin Kothari
  • 13.8k
  • 2
  • 62
  • 118

Problems that can be used to show polynomial time-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial time-time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I might try to prove that it is 3SUM-hard instead. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed takerequire $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems Ithat can usebe used for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X sosuch that I can show it is X-hard and leave it at that?

I remember reading somewhere that the generalized version of 3SUM, rSUM can be used for this purpose, at leastUpdate: This question originally asked for boundsfamilies of the form $n^k$, where $k$ is an integer. (If this information is incorrect, please point it outproblems.)

Are Since there any other natural uniformaren't that many families of problems which allow us to prove hardness results of this sort? That is, for every integer $k>0$and this question has already received excellent examples of individual hard problems, there shouldI'm relaxing the question to any problem that can be used for polynomial-time hardness results. I'm also adding a problem inbounty to this family that is conjecturedquestion to require time $\Theta(n^k)$encourage more answers. And what about running times like $n^1.5$?

Problems that can be used to show polynomial time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I prove that it is 3SUM-hard. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed take $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems I can use for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X so that I can show it is X-hard and leave it at that?

I remember reading somewhere that the generalized version of 3SUM, rSUM can be used for this purpose, at least for bounds of the form $n^k$, where $k$ is an integer. (If this information is incorrect, please point it out.)

Are there any other natural uniform families of problems which allow us to prove hardness results of this sort? That is, for every integer $k>0$, there should be a problem in this family that is conjectured to require time $\Theta(n^k)$. And what about running times like $n^1.5$?

Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial-time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I might try to prove that it is 3SUM-hard instead. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed require $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems that can be used for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X such that I can show it is X-hard and leave it at that?

Update: This question originally asked for families of problems. Since there aren't that many families of problems, and this question has already received excellent examples of individual hard problems, I'm relaxing the question to any problem that can be used for polynomial-time hardness results. I'm also adding a bounty to this question to encourage more answers.

edited tags
Link
András Salamon
  • 19.2k
  • 3
  • 65
  • 151
Source Link
Robin Kothari
  • 13.8k
  • 2
  • 62
  • 118

Problems that can be used to show polynomial time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I prove that it is 3SUM-hard. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed take $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems I can use for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X so that I can show it is X-hard and leave it at that?

I remember reading somewhere that the generalized version of 3SUM, rSUM can be used for this purpose, at least for bounds of the form $n^k$, where $k$ is an integer. (If this information is incorrect, please point it out.)

Are there any other natural uniform families of problems which allow us to prove hardness results of this sort? That is, for every integer $k>0$, there should be a problem in this family that is conjectured to require time $\Theta(n^k)$. And what about running times like $n^1.5$?