Is “Reachable Object” really an NP-complete problem?
$begingroup$
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?
complexity-theory np-complete np-hard satisfiability
edited Apr 18 at 5:11
ruakh
22417
asked Apr 17 at 8:03
InfinityInfinity
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?
complexity-theory np-complete np-hard satisfiability
edited Apr 18 at 5:11
ruakh
22417
asked Apr 17 at 8:03
InfinityInfinity
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness.
$endgroup$
– Discrete lizard♦
Apr 17 at 10:42
6
$begingroup$
I just want you to know that the symbol isin, notepsilon.
$endgroup$
– Alice Ryhl
Apr 17 at 11:15
add a comment |
$begingroup$
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?
complexity-theory np-complete np-hard satisfiability
edited Apr 18 at 5:11
ruakh
22417
asked Apr 17 at 8:03
InfinityInfinity
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?
complexity-theory np-complete np-hard satisfiability
complexity-theory np-complete np-hard satisfiability
edited Apr 18 at 5:11
ruakh
22417
asked Apr 17 at 8:03
InfinityInfinity
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 18 at 5:11
ruakh
22417
asked Apr 17 at 8:03
InfinityInfinity
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 18 at 5:11
ruakh
22417
edited Apr 18 at 5:11
ruakh
22417
edited Apr 18 at 5:11
ruakh
22417
22417
asked Apr 17 at 8:03
InfinityInfinity
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 17 at 8:03
InfinityInfinity
435
asked Apr 17 at 8:03
InfinityInfinity
435
435
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Infinity is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness.
$endgroup$
– Discrete lizard♦
Apr 17 at 10:42
6
$begingroup$
I just want you to know that the symbol isin, notepsilon.
$endgroup$
– Alice Ryhl
Apr 17 at 11:15
add a comment |
$begingroup$
The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness.
$endgroup$
– Discrete lizard♦
Apr 17 at 10:42
6
$begingroup$
I just want you to know that the symbol isin, notepsilon.
$endgroup$
– Alice Ryhl
Apr 17 at 11:15
$begingroup$
The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness.
$endgroup$
– Discrete lizard♦
Apr 17 at 10:42
$begingroup$
The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness.
$endgroup$
– Discrete lizard♦
Apr 17 at 10:42
6
6
$begingroup$
I just want you to know that the symbol is
in, not epsilon.$endgroup$
– Alice Ryhl
Apr 17 at 11:15
$begingroup$
I just want you to know that the symbol is
in, not epsilon.$endgroup$
– Alice Ryhl
Apr 17 at 11:15
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A problem $P$ is NP-complete if:
$P$ is NP-hard and
$P in textbf{NP}$.
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
$endgroup$
2
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
1
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
add a comment |
$begingroup$
The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps.
What remains to be shown is that there is a sequence of swaps that has polynomial size. Note that since each agent has strict preferences and will only swap if it can make a trade that gives it a better object, each agent can swap at most $n$ times. As there are at most $n$ agents, each sequence of swaps has at most $n^2$ swaps.
I think that if there were non-strict preferences, it might be possible that some items will have to move across long cycles to reach certain states, and that in particular there exist states where all sequences of swaps have exponential size. However, I cannot think of an immediate example of such a problem. At the least, it is no longer 'easy' to show the problem with non-strict preferences is in NP.
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Infinity 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%2f107085%2fis-reachable-object-really-an-np-complete-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A problem $P$ is NP-complete if:
$P$ is NP-hard and
$P in textbf{NP}$.
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
$endgroup$
2
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
1
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
add a comment |
$begingroup$
A problem $P$ is NP-complete if:
$P$ is NP-hard and
$P in textbf{NP}$.
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
$endgroup$
2
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
1
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
add a comment |
$begingroup$
A problem $P$ is NP-complete if:
$P$ is NP-hard and
$P in textbf{NP}$.
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
$endgroup$
A problem $P$ is NP-complete if:
$P$ is NP-hard and
$P in textbf{NP}$.
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
answered Apr 17 at 8:06
dkaeaedkaeae
2,53211123
2,53211123
2
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
1
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
add a comment |
2
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
1
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
2
2
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
$begingroup$
In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object.
$endgroup$
– Steven Lowes
Apr 17 at 12:49
1
1
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
@StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer.
$endgroup$
– Discrete lizard♦
Apr 17 at 13:49
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :)
$endgroup$
– Steven Lowes
Apr 17 at 14:55
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
$begingroup$
@StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify."
$endgroup$
– Kevin
Apr 18 at 7:03
add a comment |
$begingroup$
The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps.
What remains to be shown is that there is a sequence of swaps that has polynomial size. Note that since each agent has strict preferences and will only swap if it can make a trade that gives it a better object, each agent can swap at most $n$ times. As there are at most $n$ agents, each sequence of swaps has at most $n^2$ swaps.
I think that if there were non-strict preferences, it might be possible that some items will have to move across long cycles to reach certain states, and that in particular there exist states where all sequences of swaps have exponential size. However, I cannot think of an immediate example of such a problem. At the least, it is no longer 'easy' to show the problem with non-strict preferences is in NP.
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
$endgroup$
add a comment |
$begingroup$
The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps.
What remains to be shown is that there is a sequence of swaps that has polynomial size. Note that since each agent has strict preferences and will only swap if it can make a trade that gives it a better object, each agent can swap at most $n$ times. As there are at most $n$ agents, each sequence of swaps has at most $n^2$ swaps.
I think that if there were non-strict preferences, it might be possible that some items will have to move across long cycles to reach certain states, and that in particular there exist states where all sequences of swaps have exponential size. However, I cannot think of an immediate example of such a problem. At the least, it is no longer 'easy' to show the problem with non-strict preferences is in NP.
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
$endgroup$
add a comment |
$begingroup$
The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps.
What remains to be shown is that there is a sequence of swaps that has polynomial size. Note that since each agent has strict preferences and will only swap if it can make a trade that gives it a better object, each agent can swap at most $n$ times. As there are at most $n$ agents, each sequence of swaps has at most $n^2$ swaps.
I think that if there were non-strict preferences, it might be possible that some items will have to move across long cycles to reach certain states, and that in particular there exist states where all sequences of swaps have exponential size. However, I cannot think of an immediate example of such a problem. At the least, it is no longer 'easy' to show the problem with non-strict preferences is in NP.
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
$endgroup$
The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps.
What remains to be shown is that there is a sequence of swaps that has polynomial size. Note that since each agent has strict preferences and will only swap if it can make a trade that gives it a better object, each agent can swap at most $n$ times. As there are at most $n$ agents, each sequence of swaps has at most $n^2$ swaps.
I think that if there were non-strict preferences, it might be possible that some items will have to move across long cycles to reach certain states, and that in particular there exist states where all sequences of swaps have exponential size. However, I cannot think of an immediate example of such a problem. At the least, it is no longer 'easy' to show the problem with non-strict preferences is in NP.
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
edited Apr 18 at 5:18
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,59811538
4,59811538
add a comment |
add a comment |
Infinity is a new contributor. Be nice, and check out our Code of Conduct.
Infinity is a new contributor. Be nice, and check out our Code of Conduct.
Infinity is a new contributor. Be nice, and check out our Code of Conduct.
Infinity is a new contributor. Be nice, and check out our Code of Conduct.
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.
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%2f107085%2fis-reachable-object-really-an-np-complete-problem%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
$begingroup$
The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness.
$endgroup$
– Discrete lizard♦
Apr 17 at 10:42
6
$begingroup$
I just want you to know that the symbol is
in, notepsilon.$endgroup$
– Alice Ryhl
Apr 17 at 11:15