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 5 hours 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
4 hours 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 hours 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 hours ago
add a 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
4 hours 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 hours 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 hours ago
add a 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
4 hours 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 hours 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 hours ago
add a 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 4 hours ago
David Richerby
64.6k1597186
64.6k1597186
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
4 hours 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 hours 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 hours ago
add a 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
4 hours 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 hours 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 hours 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
4 hours 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
4 hours 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 hours 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 hours 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 hours 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 hours ago
add a 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