Ttyjukl

To string or not to string

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

Why, historically, did Gödel think CH was false?

Prove that NP is closed under karp reduction?

Can divisibility rules for digits be generalized to sum of digits

Are the number of citations and number of published articles the most important criteria for a tenure promotion?

What typically incentivizes a professor to change jobs to a lower ranking university?

How to add double frame in tcolorbox?

How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?

Voyeurism but not really

Either or Neither in sentence with another negative

How is it possible to have an ability score that is less than 3?

TGV timetables / schedules?

Schoenfled Residua test shows proportionality hazard assumptions holds but Kaplan-Meier plots intersect

Theorems that impeded progress

What does it mean to describe someone as a butt steak?

Font hinting is lost in Chrome-like browsers (for some languages )

Test whether all array elements are factors of a number

Why doesn't H₄O²⁺ exist?

Can an x86 CPU running in real mode be considered to be basically an 8086 CPU?

Characters won't fit in table

US citizen flying to France today and my passport expires in less than 2 months

Arthur Somervell: 1000 Exercises - Meaning of this notation

How to format long polynomial?

Prove that NP is closed under karp reduction?

Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbf{NC_2}$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

1

$begingroup$

A complexity class $mathbb{C}$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B in mathbb{C}$ $implies$ $A in mathbb{C}$

How would you go about proving this if $mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $A$ karp reduces to $B$ and $B in NP$ $implies$ $A in NP$

complexity-theory

share|cite|improve this question

asked 2 hours ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Try using the definitions.
  $endgroup$
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YuvalFilmus thanks for the advice, this helped me figure it out!
  $endgroup$
  – Ankit Bahl
  1 hour ago
  

  
  
  
  

add a comment | 

1

$begingroup$

A complexity class $mathbb{C}$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B in mathbb{C}$ $implies$ $A in mathbb{C}$

How would you go about proving this if $mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $A$ karp reduces to $B$ and $B in NP$ $implies$ $A in NP$

complexity-theory

share|cite|improve this question

asked 2 hours ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Try using the definitions.
  $endgroup$
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YuvalFilmus thanks for the advice, this helped me figure it out!
  $endgroup$
  – Ankit Bahl
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

A complexity class $mathbb{C}$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B in mathbb{C}$ $implies$ $A in mathbb{C}$

How would you go about proving this if $mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $A$ karp reduces to $B$ and $B in NP$ $implies$ $A in NP$

complexity-theory

share|cite|improve this question

asked 2 hours ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked 2 hours ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked 2 hours ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 hours ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 hours ago

Ankit BahlAnkit Bahl

262

1 Answer
1

active

oldest

votes

2

$begingroup$

I was able to figure it out. In case anyone was wondering:

$B in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where i is the input to $B$.

$A$ karp reducing to $B implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and vice versa),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

1. Take input $i$ and apply $m$ to yield $m(i)$
   


2. Apply $b$ with input $m(i)$
   

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.

share|cite|improve this answer

answered 1 hour ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl 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 | 

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
});


}
});

Ankit Bahl is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106574%2fprove-that-np-is-closed-under-karp-reduction%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

I was able to figure it out. In case anyone was wondering:

$B in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where i is the input to $B$.

$A$ karp reducing to $B implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and vice versa),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

1. Take input $i$ and apply $m$ to yield $m(i)$
   


2. Apply $b$ with input $m(i)$
   

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.

share|cite|improve this answer

answered 1 hour ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl 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 | 

2

$begingroup$

I was able to figure it out. In case anyone was wondering:

$B in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where i is the input to $B$.

$A$ karp reducing to $B implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and vice versa),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

1. Take input $i$ and apply $m$ to yield $m(i)$
   


2. Apply $b$ with input $m(i)$
   

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.

share|cite|improve this answer

answered 1 hour ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

I was able to figure it out. In case anyone was wondering:

$B in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where i is the input to $B$.

$A$ karp reducing to $B implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and vice versa),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

1. Take input $i$ and apply $m$ to yield $m(i)$
   


2. Apply $b$ with input $m(i)$
   

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.

share|cite|improve this answer

answered 1 hour ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

answered 1 hour ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 1 hour ago

Ankit BahlAnkit Bahl

262

New contributor

Ankit Bahl is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 1 hour ago

Ankit BahlAnkit Bahl

262