If I'm just trying to show something is NP-hard (as opposed to NP-complete) does my reduction need to be completed in polynomial time?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have a problem that I believe is NP-hard. If I reduce a NP-complete problem to it in exponential time (and not polynomial time), does that prove the problem is NP-hard?
complexity-theory
asked Nov 25 at 22:38
cccompro
82
add a comment |
up vote
1
down vote
favorite
I have a problem that I believe is NP-hard. If I reduce a NP-complete problem to it in exponential time (and not polynomial time), does that prove the problem is NP-hard?
complexity-theory
asked Nov 25 at 22:38
cccompro
82
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have a problem that I believe is NP-hard. If I reduce a NP-complete problem to it in exponential time (and not polynomial time), does that prove the problem is NP-hard?
complexity-theory
asked Nov 25 at 22:38
cccompro
82
I have a problem that I believe is NP-hard. If I reduce a NP-complete problem to it in exponential time (and not polynomial time), does that prove the problem is NP-hard?
complexity-theory
complexity-theory
asked Nov 25 at 22:38
cccompro
82
asked Nov 25 at 22:38
cccompro
82
asked Nov 25 at 22:38
cccompro
82
asked Nov 25 at 22:38
cccompro
82
asked Nov 25 at 22:38
cccompro
82
82
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Hardness/completeness is always defined with respect to a specific kind of reduction.
Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $emptyset$ and $Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $emptyset$ and $Sigma^*$, and let $X$ be in NP. We can reduce $X$ to $L$ as follows. Fix two strings $w_mathrmyesin L$ and $w_mathrmnonotin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_mathrmyes$; otherwise, it maps $xmapsto w_mathrmno$.
* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.
answered Nov 25 at 23:05
David Richerby
64.9k1597186
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
|
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Hardness/completeness is always defined with respect to a specific kind of reduction.
Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $emptyset$ and $Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $emptyset$ and $Sigma^*$, and let $X$ be in NP. We can reduce $X$ to $L$ as follows. Fix two strings $w_mathrmyesin L$ and $w_mathrmnonotin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_mathrmyes$; otherwise, it maps $xmapsto w_mathrmno$.
* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.
answered Nov 25 at 23:05
David Richerby
64.9k1597186
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
|
show 1 more comment
up vote
2
down vote
accepted
Hardness/completeness is always defined with respect to a specific kind of reduction.
Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $emptyset$ and $Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $emptyset$ and $Sigma^*$, and let $X$ be in NP. We can reduce $X$ to $L$ as follows. Fix two strings $w_mathrmyesin L$ and $w_mathrmnonotin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_mathrmyes$; otherwise, it maps $xmapsto w_mathrmno$.
* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.
answered Nov 25 at 23:05
David Richerby
64.9k1597186
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
|
show 1 more comment
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Hardness/completeness is always defined with respect to a specific kind of reduction.
Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $emptyset$ and $Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $emptyset$ and $Sigma^*$, and let $X$ be in NP. We can reduce $X$ to $L$ as follows. Fix two strings $w_mathrmyesin L$ and $w_mathrmnonotin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_mathrmyes$; otherwise, it maps $xmapsto w_mathrmno$.
* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.
answered Nov 25 at 23:05
David Richerby
64.9k1597186
Hardness/completeness is always defined with respect to a specific kind of reduction.
Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $emptyset$ and $Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $emptyset$ and $Sigma^*$, and let $X$ be in NP. We can reduce $X$ to $L$ as follows. Fix two strings $w_mathrmyesin L$ and $w_mathrmnonotin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_mathrmyes$; otherwise, it maps $xmapsto w_mathrmno$.
* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.
answered Nov 25 at 23:05
David Richerby
64.9k1597186
answered Nov 25 at 23:05
David Richerby
64.9k1597186
answered Nov 25 at 23:05
David Richerby
64.9k1597186
answered Nov 25 at 23:05
David Richerby
64.9k1597186
64.9k1597186
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
|
show 1 more comment
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
Thanks! That makes a lot of sense. But let's say I found a reduction of time O(n^k), where k is a variable such that k <= n. What complexity class would this be?
– cccompro
Nov 25 at 23:16
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
The only way you could have $kle n$ for all $n$ would be to have $k=0$ or $k=1$, and I don't think that's what you mean.
– David Richerby
Nov 26 at 1:10
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
I'm not sure how to explain it. I have a grid with k squares. The upper bound of the size of the grid is n squares.
– cccompro
Nov 26 at 1:22
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@cccompro then you have a grid with $O(n)$ squares?? No need for $k$ if we don’t need an tight bound—this is linear.
– D. Ben Knoble
Nov 26 at 4:08
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
@D.BenKnoble It's not a tight bound because the problem is packing things into the grid (it is similar to bin packing but not exactly) and I have a reduction of time O(n^k)
– cccompro
Nov 26 at 19:26
|
show 1 more comment
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f100544%2fif-im-just-trying-to-show-something-is-np-hard-as-opposed-to-np-complete-does%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
