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
Aging parents with no investments
Which Sci-Fi work first showed weapon of galactic-scale mass destruction?
What does Linus Torvalds mean when he says that Git "never ever" tracks a file?
Are there any other methods to apply to solving simultaneous equations?
What is the motivation for a law requiring 2 parties to consent for recording a conversation
What does ひと匙 mean in this manga and has it been used colloquially?
What is the meaning of the verb "bear" in this context?
Is "plugging out" electronic devices an American expression?
Where to refill my bottle in India?
Deal with toxic manager when you can't quit
Falsification in Math vs Science
Do these rules for Critical Successes and Critical Failures seem Fair?
Shouldn't "much" here be used instead of "more"?
How can I autofill dates in Excel excluding Sunday?
Delete all lines which don't have n characters before delimiter
What is the meaning of Triage in Cybersec world?
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
Resizing object distorts it (Illustrator CC 2018)
How to manage monthly salary
Did 3000BC Egyptians use meteoric iron weapons?
Apparent duplicates between Haynes service instructions and MOT
Worn-tile Scrabble
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
Is this app Icon Browser Safe/Legit?
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 14 hours ago
dkaeae
2,3421922
asked 14 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 14 hours ago
dkaeae
2,3421922
asked 14 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
14 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
13 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
11 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
10 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 14 hours ago
dkaeae
2,3421922
asked 14 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 14 hours ago
dkaeae
2,3421922
asked 14 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 14 hours ago
dkaeae
2,3421922
asked 14 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 14 hours ago
dkaeae
2,3421922
edited 14 hours ago
dkaeae
2,3421922
edited 14 hours ago
dkaeae
2,3421922
2,3421922
asked 14 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 14 hours ago
R. dVR. dV
184
asked 14 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
14 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
13 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
11 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
10 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
14 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
13 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
11 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
10 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
14 hours ago
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
14 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
13 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
13 hours ago
1
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
11 hours ago
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
11 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
10 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
10 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 14 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
14 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
13 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
12 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
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 11 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
11 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
11 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
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
8 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 14 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
14 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
13 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
12 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
11 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 14 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
14 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
13 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
12 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
11 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 14 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 14 hours ago
dkaeaedkaeae
2,3421922
edited 10 hours ago
answered 14 hours ago
dkaeaedkaeae
2,3421922
answered 14 hours ago
dkaeaedkaeae
2,3421922
answered 14 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
14 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
13 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
12 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
11 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
14 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
13 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
12 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
11 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
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
14 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
13 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
13 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
12 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
12 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
11 hours ago
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
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 11 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
11 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
11 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
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
8 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 11 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
11 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
11 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
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
8 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 11 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 11 hours ago
David RicherbyDavid Richerby
70k15106196
answered 11 hours ago
David RicherbyDavid Richerby
70k15106196
answered 11 hours ago
David RicherbyDavid Richerby
70k15106196
answered 11 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
11 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
11 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
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
8 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
11 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
11 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
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
8 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
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
11 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
11 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
11 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
10 hours ago
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
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
8 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
8 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
14 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
13 hours ago
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
11 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
10 hours ago