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?
How often does castling occur in grandmaster games?
What does this say in Elvish?
Should a wizard buy fine inks every time he want to copy spells into his spellbook?
How does light 'choose' between wave and particle behaviour?
One-one communication
Lagrange four-squares theorem --- deterministic complexity
Tannaka duality for semisimple groups
How to report t statistic from R
The test team as an enemy of development? And how can this be avoided?
Can the Flaming Sphere spell be rammed into multiple Tiny creatures that are in the same 5-foot square?
Time evolution of a Gaussian wave packet, why convert to k-space?
Girl Hackers - Logic Puzzle
How does the math work when buying airline miles?
Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?
Dynamic filling of a region of a polar plot
Trademark violation for app?
Does the Mueller report show a conspiracy between Russia and the Trump Campaign?
Did Mueller's report provide an evidentiary basis for the claim of Russian govt election interference via social media?
What's the point of the test set?
Sum letters are not two different
What would you call this weird metallic apparatus that allows you to lift people?
How do living politicians protect their readily obtainable signatures from misuse?
Getting prompted for verification code but where do I put it in?
Putting class ranking in CV, but against dept guidelines
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 yesterday
ruakh
22417
asked 2 days ago
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 yesterday
ruakh
22417
asked 2 days ago
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♦
2 days ago
6
$begingroup$
I just want you to know that the symbol isin, notepsilon.
$endgroup$
– Alice Ryhl
2 days ago
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 yesterday
ruakh
22417
asked 2 days ago
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 yesterday
ruakh
22417
asked 2 days ago
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 yesterday
ruakh
22417
asked 2 days ago
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 yesterday
ruakh
22417
edited yesterday
ruakh
22417
edited yesterday
ruakh
22417
22417
asked 2 days ago
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 2 days ago
InfinityInfinity
435
asked 2 days ago
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♦
2 days ago
6
$begingroup$
I just want you to know that the symbol isin, notepsilon.
$endgroup$
– Alice Ryhl
2 days ago
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♦
2 days ago
6
$begingroup$
I just want you to know that the symbol isin, notepsilon.
$endgroup$
– Alice Ryhl
2 days ago
$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♦
2 days ago
$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♦
2 days ago
6
6
$begingroup$
I just want you to know that the symbol is
in, not epsilon.$endgroup$
– Alice Ryhl
2 days ago
$begingroup$
I just want you to know that the symbol is
in, not epsilon.$endgroup$
– Alice Ryhl
2 days ago
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 2 days ago
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
2 days ago
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♦
2 days ago
$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
2 days ago
$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
yesterday
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 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
$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 2 days ago
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
2 days ago
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♦
2 days ago
$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
2 days ago
$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
yesterday
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 2 days ago
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
2 days ago
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♦
2 days ago
$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
2 days ago
$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
yesterday
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 2 days ago
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 2 days ago
dkaeaedkaeae
2,53211123
answered 2 days ago
dkaeaedkaeae
2,53211123
answered 2 days ago
dkaeaedkaeae
2,53211123
answered 2 days ago
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
2 days ago
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♦
2 days ago
$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
2 days ago
$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
yesterday
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
2 days ago
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♦
2 days ago
$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
2 days ago
$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
yesterday
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
2 days ago
$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
2 days ago
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♦
2 days ago
$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♦
2 days ago
$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
2 days ago
$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
2 days ago
$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
yesterday
$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
yesterday
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 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
$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 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
$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 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
$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 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
edited yesterday
answered 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
answered 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
answered 2 days ago
Discrete lizard♦Discrete lizard
4,59011538
4,59011538
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♦
2 days ago
6
$begingroup$
I just want you to know that the symbol is
in, notepsilon.$endgroup$
– Alice Ryhl
2 days ago