Ttdfjt

Is it possible to make sharp wind that can cut stuff from afar?

Why Is Death Allowed In the Matrix?

Can I make popcorn with any corn?

Why CLRS example on residual networks does not follows its formula?

DOS, create pipe for stdin/stdout of command.com(or 4dos.com) in C or Batch?

My colleague's body is amazing

Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).

The use of multiple foreign keys on same column in SQL Server

What would happen to a modern skyscraper if it rains micro blackholes?

Japan - Plan around max visa duration

Example of a relative pronoun

How to make payment on the internet without leaving a money trail?

Can town administrative "code" overule state laws like those forbidding trespassing?

Banach space and Hilbert space topology

How can the DM most effectively choose 1 out of an odd number of players to be targeted by an attack or effect?

How to report a triplet of septets in NMR tabulation?

How can bays and straits be determined in a procedurally generated map?

Simulate Bitwise Cyclic Tag

How old can references or sources in a thesis be?

What defenses are there against being summoned by the Gate spell?

What are these boxed doors outside store fronts in New York?

Non-Jewish family in an Orthodox Jewish Wedding

least quadratic residue under GRH: an EXPLICIT bound

Can a German sentence have two subjects?

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$mathbfNC_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?

4

0

$begingroup$

A complexity class $mathbbC$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B in mathbbC$ $implies$ $A in mathbbC$

How would you go about proving this if $mathbbC = 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 yesterday

Ankit BahlAnkit Bahl

814

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$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  Try using the definitions.
  $endgroup$
  – Yuval Filmus
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

4

0

$begingroup$

A complexity class $mathbbC$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B in mathbbC$ $implies$ $A in mathbbC$

How would you go about proving this if $mathbbC = 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 yesterday

Ankit BahlAnkit Bahl

814

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$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  Try using the definitions.
  $endgroup$
  – Yuval Filmus
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

$begingroup$

A complexity class $mathbbC$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B in mathbbC$ $implies$ $A in mathbbC$

How would you go about proving this if $mathbbC = 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 yesterday

Ankit BahlAnkit Bahl

814

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 yesterday

Ankit BahlAnkit Bahl

814

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 yesterday

Ankit BahlAnkit Bahl

814

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 yesterday

Ankit BahlAnkit Bahl

814

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 yesterday

Ankit BahlAnkit Bahl

814

1 Answer
1

active

oldest

votes

6

$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 same for false case),

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

edited 5 hours ago

answered yesterday

Ankit BahlAnkit Bahl

814

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

6

$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 same for false case),

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

edited 5 hours ago

answered yesterday

Ankit BahlAnkit Bahl

814

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 | 

6

$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 same for false case),

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

edited 5 hours ago

answered yesterday

Ankit BahlAnkit Bahl

814

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 same for false case),

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

edited 5 hours ago

answered yesterday

Ankit BahlAnkit Bahl

814

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

edited 5 hours ago

answered yesterday

Ankit BahlAnkit Bahl

814

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 yesterday

Ankit BahlAnkit Bahl

814

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 yesterday

Ankit BahlAnkit Bahl

814