Is the empty problem (or its complement) Karp reducible to any problem in NP? Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?If 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
Why was the term "discrete" used in discrete logarithm?
Disable hyphenation for an entire paragraph
Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?
Bonus calculation: Am I making a mountain out of a molehill?
Does accepting a pardon have any bearing on trying that person for the same crime in a sovereign jurisdiction?
Why constant symbols in a language?
What is the longest distance a 13th-level monk can jump while attacking on the same turn?
Do I really need recursive chmod to restrict access to a folder?
Is there a "higher Segal conjecture"?
Is the Standard Deduction better than Itemized when both are the same amount?
If a contract sometimes uses the wrong name, is it still valid?
When -s is used with third person singular. What's its use in this context?
Diagram with tikz
How to find all the available tools in macOS terminal?
Is it true that "carbohydrates are of no use for the basal metabolic need"?
Why is "Consequences inflicted." not a sentence?
Proof involving the spectral radius and the Jordan canonical form
Stars Make Stars
Why are there no cargo aircraft with "flying wing" design?
Check which numbers satisfy the condition [A*B*C = A! + B! + C!]
What is a Meta algorithm?
Does surprise arrest existing movement?
Using et al. for a last / senior author rather than for a first author
Is there a service that would inform me whenever a new direct route is scheduled from a given airport?
Is the empty problem (or its complement) Karp reducible to any problem in NP?
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?If 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 Apr 10 at 11:57
dkaeae
2,36211022
asked Apr 10 at 11:43
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 Apr 10 at 11:57
dkaeae
2,36211022
asked Apr 10 at 11:43
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
Apr 10 at 12:14
$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
Apr 10 at 12:26
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
Apr 10 at 14:32
$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
Apr 10 at 15:59
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 Apr 10 at 11:57
dkaeae
2,36211022
asked Apr 10 at 11:43
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 Apr 10 at 11:57
dkaeae
2,36211022
asked Apr 10 at 11:43
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 Apr 10 at 11:57
dkaeae
2,36211022
asked Apr 10 at 11:43
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 Apr 10 at 11:57
dkaeae
2,36211022
edited Apr 10 at 11:57
dkaeae
2,36211022
edited Apr 10 at 11:57
dkaeae
2,36211022
2,36211022
asked Apr 10 at 11:43
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 Apr 10 at 11:43
R. dVR. dV
184
asked Apr 10 at 11:43
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
Apr 10 at 12:14
$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
Apr 10 at 12:26
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
Apr 10 at 14:32
$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
Apr 10 at 15:59
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
Apr 10 at 12:14
$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
Apr 10 at 12:26
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
Apr 10 at 14:32
$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
Apr 10 at 15:59
1
1
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
Apr 10 at 12:14
$begingroup$
You don't even need to assume $P=NP$ for this. Just take $A=B$.
$endgroup$
– Tom van der Zanden
Apr 10 at 12:14
$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
Apr 10 at 12:26
$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
Apr 10 at 12:26
1
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
Apr 10 at 14:32
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
Apr 10 at 14:32
$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
Apr 10 at 15:59
$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
Apr 10 at 15:59
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 Apr 10 at 11:55
dkaeaedkaeae
2,36211022
$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
Apr 10 at 12:03
$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
Apr 10 at 13:12
$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
Apr 10 at 13:52
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
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 Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
$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
Apr 10 at 15:18
$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
Apr 10 at 15:24
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$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
Apr 10 at 18:01
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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 Apr 10 at 11:55
dkaeaedkaeae
2,36211022
$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
Apr 10 at 12:03
$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
Apr 10 at 13:12
$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
Apr 10 at 13:52
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
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 Apr 10 at 11:55
dkaeaedkaeae
2,36211022
$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
Apr 10 at 12:03
$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
Apr 10 at 13:12
$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
Apr 10 at 13:52
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
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 Apr 10 at 11:55
dkaeaedkaeae
2,36211022
$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 Apr 10 at 11:55
dkaeaedkaeae
2,36211022
edited Apr 10 at 15:56
answered Apr 10 at 11:55
dkaeaedkaeae
2,36211022
answered Apr 10 at 11:55
dkaeaedkaeae
2,36211022
answered Apr 10 at 11:55
dkaeaedkaeae
2,36211022
2,36211022
$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
Apr 10 at 12:03
$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
Apr 10 at 13:12
$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
Apr 10 at 13:52
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
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
Apr 10 at 12:03
$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
Apr 10 at 13:12
$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
Apr 10 at 13:52
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
$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
Apr 10 at 12:03
$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
Apr 10 at 12:03
$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
Apr 10 at 13:12
$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
Apr 10 at 13:12
$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
Apr 10 at 13:52
$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
Apr 10 at 13:52
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
$begingroup$
Re your note at the end, you can't reduce between $emptyset$ and $Sigma^*$, either.
$endgroup$
– David Richerby
Apr 10 at 14:33
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 Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
$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
Apr 10 at 15:18
$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
Apr 10 at 15:24
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$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
Apr 10 at 18:01
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 Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
$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
Apr 10 at 15:18
$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
Apr 10 at 15:24
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$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
Apr 10 at 18:01
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 Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
$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 Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
answered Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
answered Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
answered Apr 10 at 14:31
David RicherbyDavid Richerby
70.4k16107196
70.4k16107196
$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
Apr 10 at 15:18
$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
Apr 10 at 15:24
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$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
Apr 10 at 18:01
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
Apr 10 at 15:18
$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
Apr 10 at 15:24
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$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
Apr 10 at 18:01
$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
Apr 10 at 15:18
$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
Apr 10 at 15:18
$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
Apr 10 at 15:24
$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
Apr 10 at 15:24
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$begingroup$
Or $A$ union a finite set if $A$ is a singleton.
$endgroup$
– David Richerby
Apr 10 at 15:59
$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
Apr 10 at 18:01
$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
Apr 10 at 18:01
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
Apr 10 at 12:14
$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
Apr 10 at 12:26
1
$begingroup$
@R.dV It's irrelevant even if you assume $Aneq B$.
$endgroup$
– David Richerby
Apr 10 at 14:32
$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
Apr 10 at 15:59