Is the empty problem (or its complement) Karp reducible to any problem in NP?
$begingroup$
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:
If $textbf{P}=textbf{NP}$, the following holds:
For every $A in textbf{NP}$, there is a $B in textbf{NP}$ such that $A leq B$ (where $leq$ means Karp reducible).
However, I do not understand how this applies to the empty problem $emptyset$, and it's complement $Sigma^*$, as these only have no-instances and yes-instances, respectively.
Are there other problems in NP such that these two are reducible to them?
complexity-theory reductions
edited 16 hours ago
dkaeae
2,3421922
asked 16 hours ago
R. dVR. dV
184
New contributor
R. dV 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'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:
If $textbf{P}=textbf{NP}$, the following holds:
For every $A in textbf{NP}$, there is a $B in textbf{NP}$ such that $A leq B$ (where $leq$ means Karp reducible).
However, I do not understand how this applies to the empty problem $emptyset$, and it's complement $Sigma^*$, as these only have no-instances and yes-instances, respectively.
Are there other problems in NP such that these two are reducible to them?
complexity-theory reductions
edited 16 hours ago
dkaeae
2,3421922
asked 16 hours ago
R. dVR. dV
184
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
16 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbf{A} neq textbf{B}$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
16 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
@R.dV Adding to David Richerby's comment: $B neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A setminus { w }$, where $w in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A cup { w }$, where $w notin A$ and $A neq Sigma^ast setminus { w }$).
$endgroup$
– dkaeae
12 hours ago
add a comment |
$begingroup$
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:
If $textbf{P}=textbf{NP}$, the following holds:
For every $A in textbf{NP}$, there is a $B in textbf{NP}$ such that $A leq B$ (where $leq$ means Karp reducible).
However, I do not understand how this applies to the empty problem $emptyset$, and it's complement $Sigma^*$, as these only have no-instances and yes-instances, respectively.
Are there other problems in NP such that these two are reducible to them?
complexity-theory reductions
edited 16 hours ago
dkaeae
2,3421922
asked 16 hours ago
R. dVR. dV
184
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:
If $textbf{P}=textbf{NP}$, the following holds:
For every $A in textbf{NP}$, there is a $B in textbf{NP}$ such that $A leq B$ (where $leq$ means Karp reducible).
However, I do not understand how this applies to the empty problem $emptyset$, and it's complement $Sigma^*$, as these only have no-instances and yes-instances, respectively.
Are there other problems in NP such that these two are reducible to them?
complexity-theory reductions
complexity-theory reductions
edited 16 hours ago
dkaeae
2,3421922
asked 16 hours ago
R. dVR. dV
184
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 16 hours ago
dkaeae
2,3421922
asked 16 hours ago
R. dVR. dV
184
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 16 hours ago
dkaeae
2,3421922
edited 16 hours ago
dkaeae
2,3421922
edited 16 hours ago
dkaeae
2,3421922
2,3421922
asked 16 hours ago
R. dVR. dV
184
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
R. dVR. dV
184
asked 16 hours ago
R. dVR. dV
184
184
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
R. dV is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
16 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbf{A} neq textbf{B}$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
16 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
@R.dV Adding to David Richerby's comment: $B neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A setminus { w }$, where $w in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A cup { w }$, where $w notin A$ and $A neq Sigma^ast setminus { w }$).
$endgroup$
– dkaeae
12 hours ago
add a comment |
1
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
16 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbf{A} neq textbf{B}$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
16 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
@R.dV Adding to David Richerby's comment: $B neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A setminus { w }$, where $w in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A cup { w }$, where $w notin A$ and $A neq Sigma^ast setminus { w }$).
$endgroup$
– dkaeae
12 hours ago
1
1
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
16 hours ago
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
16 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbf{A} neq textbf{B}$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
16 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbf{A} neq textbf{B}$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
16 hours ago
1
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
@R.dV Adding to David Richerby's comment: $B neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A setminus { w }$, where $w in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A cup { w }$, where $w notin A$ and $A neq Sigma^ast setminus { w }$).
$endgroup$
– dkaeae
12 hours ago
$begingroup$
@R.dV Adding to David Richerby's comment: $B neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A setminus { w }$, where $w in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A cup { w }$, where $w notin A$ and $A neq Sigma^ast setminus { w }$).
$endgroup$
– dkaeae
12 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Of course there is.
Just take any non-trivial language $L$ (i.e., $L neq varnothing$ and $L neq Sigma^ast$). Then there are concrete words $x in L$ and $y notin L$.
To reduce $varnothing$ to $L$, simply map everything to $y$. Then the input is in $varnothing$ (which is false) if and only if $y in L$ (which is also false). Hence, the reduction is correct.
For $Sigma^ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $textbf{P} = textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $varnothing$ or $Sigma^ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
answered 16 hours ago
dkaeaedkaeae
2,3421922
$endgroup$
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
add a comment |
$begingroup$
The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $B=A$.
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
$endgroup$
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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
});
}
});
R. dV 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%2f106771%2fis-the-empty-problem-or-its-complement-karp-reducible-to-any-problem-in-np%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$
Of course there is.
Just take any non-trivial language $L$ (i.e., $L neq varnothing$ and $L neq Sigma^ast$). Then there are concrete words $x in L$ and $y notin L$.
To reduce $varnothing$ to $L$, simply map everything to $y$. Then the input is in $varnothing$ (which is false) if and only if $y in L$ (which is also false). Hence, the reduction is correct.
For $Sigma^ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $textbf{P} = textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $varnothing$ or $Sigma^ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
answered 16 hours ago
dkaeaedkaeae
2,3421922
$endgroup$
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
add a comment |
$begingroup$
Of course there is.
Just take any non-trivial language $L$ (i.e., $L neq varnothing$ and $L neq Sigma^ast$). Then there are concrete words $x in L$ and $y notin L$.
To reduce $varnothing$ to $L$, simply map everything to $y$. Then the input is in $varnothing$ (which is false) if and only if $y in L$ (which is also false). Hence, the reduction is correct.
For $Sigma^ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $textbf{P} = textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $varnothing$ or $Sigma^ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
answered 16 hours ago
dkaeaedkaeae
2,3421922
$endgroup$
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
add a comment |
$begingroup$
Of course there is.
Just take any non-trivial language $L$ (i.e., $L neq varnothing$ and $L neq Sigma^ast$). Then there are concrete words $x in L$ and $y notin L$.
To reduce $varnothing$ to $L$, simply map everything to $y$. Then the input is in $varnothing$ (which is false) if and only if $y in L$ (which is also false). Hence, the reduction is correct.
For $Sigma^ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $textbf{P} = textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $varnothing$ or $Sigma^ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
answered 16 hours ago
dkaeaedkaeae
2,3421922
$endgroup$
Of course there is.
Just take any non-trivial language $L$ (i.e., $L neq varnothing$ and $L neq Sigma^ast$). Then there are concrete words $x in L$ and $y notin L$.
To reduce $varnothing$ to $L$, simply map everything to $y$. Then the input is in $varnothing$ (which is false) if and only if $y in L$ (which is also false). Hence, the reduction is correct.
For $Sigma^ast$, do the same but use $x$ instead.
As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $textbf{P} = textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $varnothing$ or $Sigma^ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).
answered 16 hours ago
dkaeaedkaeae
2,3421922
edited 12 hours ago
answered 16 hours ago
dkaeaedkaeae
2,3421922
answered 16 hours ago
dkaeaedkaeae
2,3421922
answered 16 hours ago
dkaeaedkaeae
2,3421922
2,3421922
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
add a comment |
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
Hey @dkaeae, thanks for responding. I thought about something like this, but as far as I knew, this wasn't correct, since we're not mapping the yes-instances from L (so, x $in$ L) to anything in $emptyset$, and vice versa. I don't see how we're mapping yes instances from f(I) to yes-instances of I, as there are no yes-instances of I. I learned that for any karp reduction A $leq$ to be correct, you need two things: For I $in$ as a yes-instance, f(i) $in$ B should be a yes-instance, and vice versa. How could we then map f(i) yes instances to yes instances of I, if I has none?
$endgroup$
– R. dV
16 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
You seem to have it the other way around. If you are reducing $varnothing$ to $L$, then you should be mapping yes-instances of $varnothing$ to yes-instances of $L$ and no-instances to no-instances of $L$. There are no yes-instances of $varnothing$; hence, everything is a no-instance and we can afford mapping everything to the same no-instance $y notin L$.
$endgroup$
– dkaeae
15 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Yes, that's true, but we were shown that the contraposition of mapping no instances of I -> f(I) is to map yes-instances of f(I) -> I. This was ofcourse done with problems that have yes and no instances. But given your answers, I see now how it works for non-trivial languages. Thanks again :)
$endgroup$
– R. dV
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
14 hours ago
add a comment |
$begingroup$
The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $B=A$.
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
$endgroup$
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
add a comment |
$begingroup$
The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $B=A$.
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
$endgroup$
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
add a comment |
$begingroup$
The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $B=A$.
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
$endgroup$
The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $B=A$.
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
answered 14 hours ago
David RicherbyDavid Richerby
70k15106196
70k15106196
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
add a comment |
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
Hi David, Tom already commented this on the question, as I stated there, the assumption I made for this questions is that $textbf{B}neqtextbf{A}$
$endgroup$
– R. dV
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
@R.dV OK but that's your assumption and it's not included in the question you say you came across.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
12 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
$begingroup$
Yeah that's correct David, I did not get any further context from the statement; but given the difficulty they usually propose, such a trivial answer wouldn't make a lot of sense. Anyway, your last comment does make sense, so thanks :)
$endgroup$
– R. dV
10 hours ago
add a comment |
R. dV is a new contributor. Be nice, and check out our Code of Conduct.
R. dV is a new contributor. Be nice, and check out our Code of Conduct.
R. dV is a new contributor. Be nice, and check out our Code of Conduct.
R. dV 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%2f106771%2fis-the-empty-problem-or-its-complement-karp-reducible-to-any-problem-in-np%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
1
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
16 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbf{A} neq textbf{B}$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
16 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
14 hours ago
$begingroup$
@R.dV Adding to David Richerby's comment: $B neq A$ is irrelevant since you could just take an arbitrary $A$ and set $B$ to $A$ minus a finite set (e.g., $A setminus { w }$, where $w in A$ and $|A| > 1$) or $A$ plus a finite set not in $A$ (e.g., $A cup { w }$, where $w notin A$ and $A neq Sigma^ast setminus { w }$).
$endgroup$
– dkaeae
12 hours ago