If I'm just trying to show something is NP-hard (as opposed to NP-complete) does my reduction need to be...
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
New contributor
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
New contributor
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
New contributor
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
New contributor
New contributor
New contributor
asked 2 days ago
cccompro
82
82
New contributor
New contributor
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_{mathrm{yes}}in L$ and $w_{mathrm{no}}notin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_{mathrm{yes}}$; otherwise, it maps $xmapsto w_{mathrm{no}}$.
* 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.
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
2 days ago
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
2 days ago
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
2 days ago
@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
2 days ago
@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
yesterday
|
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_{mathrm{yes}}in L$ and $w_{mathrm{no}}notin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_{mathrm{yes}}$; otherwise, it maps $xmapsto w_{mathrm{no}}$.
* 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.
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
2 days ago
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
2 days ago
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
2 days ago
@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
2 days ago
@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
yesterday
|
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_{mathrm{yes}}in L$ and $w_{mathrm{no}}notin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_{mathrm{yes}}$; otherwise, it maps $xmapsto w_{mathrm{no}}$.
* 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.
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
2 days ago
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
2 days ago
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
2 days ago
@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
2 days ago
@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
yesterday
|
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_{mathrm{yes}}in L$ and $w_{mathrm{no}}notin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_{mathrm{yes}}$; otherwise, it maps $xmapsto w_{mathrm{no}}$.
* 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.
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_{mathrm{yes}}in L$ and $w_{mathrm{no}}notin L$. Now, given a string $x$, we can determine in exponential time if $xin X$. If it is, the reduction maps $xmapsto w_{mathrm{yes}}$; otherwise, it maps $xmapsto w_{mathrm{no}}$.
* 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 2 days ago
David Richerby
64.7k1597186
64.7k1597186
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
2 days ago
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
2 days ago
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
2 days ago
@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
2 days ago
@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
yesterday
|
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
2 days ago
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
2 days ago
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
2 days ago
@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
2 days ago
@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
yesterday
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
2 days ago
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
2 days ago
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
2 days ago
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
2 days ago
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
2 days ago
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
2 days ago
@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
2 days ago
@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
2 days ago
@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
yesterday
@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
yesterday
|
show 1 more comment
cccompro is a new contributor. Be nice, and check out our Code of Conduct.
cccompro is a new contributor. Be nice, and check out our Code of Conduct.
cccompro is a new contributor. Be nice, and check out our Code of Conduct.
cccompro is a new contributor. Be nice, and check out our Code of Conduct.
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