Is “Reachable Object” really an NP-complete problem? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30 pm 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?
How can I wire a 9-position switch so that each position turns on one more LED than the one before?
How did Elite on the NES work?
My admission is revoked after accepting the admission offer
All ASCII characters with a given bit count
Israeli soda type drink
Why I cannot instantiate a class whose constructor is private in a friend class?
How to begin with a paragraph in latex
What to do with someone that cheated their way though university and a PhD program?
Was Objective-C really a hindrance to Apple software development?
Marquee sign letters
Is there a possibility to generate a list dynamically in Latex?
What is the ongoing value of the Kanban board to the developers as opposed to management
"Working on a knee"
Putting Ant-Man on house arrest
Why is water being consumed when my shutoff valve is closed?
Will temporary Dex penalties prevent you from getting the benefits of the "Two Weapon Fighting" feat if your Dex score falls below the prerequisite?
Simulate round-robin tournament draw
Is there a way to fake a method response using Mock or Stubs?
How to translate "red flag" into Spanish?
When speaking, how do you change your mind mid-sentence?
Could a cockatrice have parasitic embryos?
What's called a person who works as someone who puts products on shelves in stores?
How was Lagrange appointed professor of mathematics so early?
How would it unbalance gameplay to rule that Weapon Master allows for picking a fighting style?
Is “Reachable Object” really an NP-complete problem?
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30 pm 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,74311539
$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,74311539
$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,74311539
$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,74311539
$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,74311539
edited Apr 18 at 5:18
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,74311539
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,74311539
answered Apr 17 at 10:36
Discrete lizard♦Discrete lizard
4,74311539
4,74311539
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