Is “Reachable Object” really an NP-complete problem? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SATHardness of counting solutions to NP-Complete problems, assuming a type of reductionCan one reduce a problem of unknown complexity to a hard problem to show hardness?NP Completeness of 3-SAT problemWhy do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proofDirect NP-Complete proofsThe initial NP-complete problemProving NP-Complete HelpProof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)How to use SAT reductions to prove set-splitting problem is NP-Complete?
Why does BitLocker not use RSA?
Can two people see the same photon?
"Destructive power" carried by a B-52?
An isoperimetric-type inequality inside a cube
Why is there so little support for joining EFTA in the British parliament?
Statistical analysis applied to methods coming out of Machine Learning
How much damage would a cupful of neutron star matter do to the Earth?
Is there a verb for listening stealthily?
French equivalents of おしゃれは足元から (Every good outfit starts with the shoes)
How to make an animal which can only breed for a certain number of generations?
Is there a spell that can create a permanent fire?
malloc in main() or malloc in another function: allocating memory for a struct and its members
Besides transaction validation, are there any other uses of the Script language in Bitcoin
How does the body cool itself in a stillsuit?
My mentor says to set image to Fine instead of RAW — how is this different from JPG?
How to resize main filesystem
Twin's vs. Twins'
Why not use the yoke to control yaw, as well as pitch and roll?
Does the main washing effect of soap come from foam?
Is this Kuo-toa homebrew race balanced?
Why complex landing gears are used instead of simple, reliable and light weight muscle wire or shape memory alloys?
NIntegrate on a solution of a matrix ODE
Is this Half-dragon Quaggoth boss monster balanced?
What did Turing mean when saying that "machines cannot give rise to surprises" is due to a fallacy?
Is “Reachable Object” really an NP-complete problem?
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SATHardness of counting solutions to NP-Complete problems, assuming a type of reductionCan one reduce a problem of unknown complexity to a hard problem to show hardness?NP Completeness of 3-SAT problemWhy do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proofDirect NP-Complete proofsThe initial NP-complete problemProving NP-Complete HelpProof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)How to use SAT reductions to prove set-splitting problem is NP-Complete?
$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 textbfNP$.
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 textbfNP$.
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 textbfNP$.
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 textbfNP$.
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 textbfNP$.
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