Is the empty problem (or its complement) Karp reducible to any problem in NP? The 2019 Stack Overflow Developer Survey Results Are InIf A is mapping reducible to B then the complement of A is mapping reducible to the complement of BNon-self-reducible NP problemWhat can I deduce if an NP-complete problem is reducible to its complement?EQtm is not mapping reducible to its complementShow that the Halting problem is reducible to its complementAre all decidable languages mapping reducible to its complement?Is it always possible to have one part of the reduction?Reduction function from A to its complementReduce EXACT 3-SET COVER to a Crossword PuzzleDefining Gap Problems
Did 3000BC Egyptians use meteoric iron weapons?
Why do UK politicians seemingly ignore opinion polls on Brexit?
Can a rogue use sneak attack with weapons that have the thrown property even if they are not thrown?
How to notate time signature switching consistently every measure
Is a "Democratic" Oligarchy-Style System Possible?
What does Linus Torvalds mean when he says that Git "never ever" tracks a file?
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
Where to refill my bottle in India?
Loose spokes after only a few rides
What is the accessibility of a package's `Private` context variables?
What is the meaning of Triage in Cybersec world?
What are the motivations for publishing new editions of an existing textbook, beyond new discoveries in a field?
Can one be advised by a professor who is very far away?
What is the motivation for a law requiring 2 parties to consent for recording a conversation
Who coined the term "madman theory"?
Can a flute soloist sit?
Why isn't airport relocation done gradually?
How to support a colleague who finds meetings extremely tiring?
Have you ever entered Singapore using a different passport or name?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
The difference between dialogue marks
How are circuits which use complex ICs normally simulated?
How technical should a Scrum Master be to effectively remove impediments?
"as much details as you can remember"
Is the empty problem (or its complement) Karp reducible to any problem in NP?
The 2019 Stack Overflow Developer Survey Results Are InIf A is mapping reducible to B then the complement of A is mapping reducible to the complement of BNon-self-reducible NP problemWhat can I deduce if an NP-complete problem is reducible to its complement?EQtm is not mapping reducible to its complementShow that the Halting problem is reducible to its complementAre all decidable languages mapping reducible to its complement?Is it always possible to have one part of the reduction?Reduction function from A to its complementReduce EXACT 3-SET COVER to a Crossword PuzzleDefining Gap Problems
$begingroup$
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:
If $textbfP=textbfNP$, the following holds:
For every $A in textbfNP$, there is a $B in textbfNP$ 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 17 hours ago
dkaeae
2,3421922
asked 18 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 $textbfP=textbfNP$, the following holds:
For every $A in textbfNP$, there is a $B in textbfNP$ 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 17 hours ago
dkaeae
2,3421922
asked 18 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
17 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbfA neq textbfB$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
17 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
15 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
13 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 $textbfP=textbfNP$, the following holds:
For every $A in textbfNP$, there is a $B in textbfNP$ 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 17 hours ago
dkaeae
2,3421922
asked 18 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 $textbfP=textbfNP$, the following holds:
For every $A in textbfNP$, there is a $B in textbfNP$ 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 17 hours ago
dkaeae
2,3421922
asked 18 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 17 hours ago
dkaeae
2,3421922
asked 18 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 17 hours ago
dkaeae
2,3421922
edited 17 hours ago
dkaeae
2,3421922
edited 17 hours ago
dkaeae
2,3421922
2,3421922
asked 18 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 18 hours ago
R. dVR. dV
184
asked 18 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
17 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbfA neq textbfB$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
17 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
15 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
13 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
17 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbfA neq textbfB$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
17 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
15 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
13 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
17 hours ago
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
17 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbfA neq textbfB$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
17 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbfA neq textbfB$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
17 hours ago
1
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
15 hours ago
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
15 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
13 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
13 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 $textbfP = textbfNP$ 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 18 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
17 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
16 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
16 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 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 15 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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
14 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 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
11 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 $textbfP = textbfNP$ 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 18 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
17 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
16 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
16 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 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 $textbfP = textbfNP$ 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 18 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
17 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
16 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
16 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 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 $textbfP = textbfNP$ 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 18 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 $textbfP = textbfNP$ 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 18 hours ago
dkaeaedkaeae
2,3421922
edited 14 hours ago
answered 18 hours ago
dkaeaedkaeae
2,3421922
answered 18 hours ago
dkaeaedkaeae
2,3421922
answered 18 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
17 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
16 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
16 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 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
17 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
16 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
16 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 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
17 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
17 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
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
16 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
16 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
16 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
15 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 15 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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
14 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 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
11 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 15 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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
14 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 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
11 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 15 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 15 hours ago
David RicherbyDavid Richerby
70k15106196
answered 15 hours ago
David RicherbyDavid Richerby
70k15106196
answered 15 hours ago
David RicherbyDavid Richerby
70k15106196
answered 15 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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
14 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 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
11 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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
14 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 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
11 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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 $textbfBneqtextbfA$
$endgroup$
– R. dV
14 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
14 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
14 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
13 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
11 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
11 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
17 hours ago
$begingroup$
Hey Tom, I think that the statement from the course meant that $textbfA neq textbfB$. Otherwise, it is indeed an irrelevant requirement.
$endgroup$
– R. dV
17 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
15 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
13 hours ago