Trjtdtk

Pulling the rope with one hand is as heavy as with two hands?

What term is being referred to with "reflected-sound-of-underground-spirits"?

Extension of 2-adic valuation to the real numbers

What is the term for a person whose job is to place products on shelves in stores?

Can someone publish a story that happened to you?

Elements that can bond to themselves?

Function pointer with named arguments?

'It addicted me, with one taste.' Can 'addict' be used transitively?

How could Tony Stark make this in Endgame?

What happens in the secondary winding if there's no spark plug connected?

How can I practically buy stocks?

Apparently, my CLR assembly function is causing deadlocks?

I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?

Why did some of my point & shoot film photos come back with one third light white or orange?

How come there are so many candidates for the 2020 Democratic party presidential nomination?

What is the optimal strategy for the Dictionary Game?

How exactly does Hawking radiation decrease the mass of black holes?

Pre-plastic human skin alternative

Which big number is bigger?

Random Forest different results for same observation

What is the most expensive material in the world that could be used to create Pun-Pun's lute?

If a planet has 3 moons, is it possible to have triple Full/New Moons at once?

As an international instructor, should I openly talk about my accent?

Who was the lone kid in the line of people at the lake at the end of Avengers: Endgame?

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?

5

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 Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

$endgroup$

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  Try using the definitions.
  $endgroup$
  – Yuval Filmus
  Apr 6 at 19:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YuvalFilmus thanks for the advice, this helped me figure it out!
  $endgroup$
  – Ankit Bahl
  Apr 6 at 20:06
  

  
  
  
  

add a comment | 

5

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 Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

$endgroup$

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  Try using the definitions.
  $endgroup$
  – Yuval Filmus
  Apr 6 at 19:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YuvalFilmus thanks for the advice, this helped me figure it out!
  $endgroup$
  – Ankit Bahl
  Apr 6 at 20:06
  

  
  
  
  

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 Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

$endgroup$

share|cite|improve this question

asked Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

share|cite|improve this question

asked Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

asked Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

asked Apr 6 at 19:02

Ankit BahlAnkit Bahl

965

1 Answer
1

active

oldest

votes

7

$begingroup$

I was able to figure it out. In case anyone (mans in ECE 406) 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 Apr 9 at 12:18

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965

$endgroup$

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



);

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

7

$begingroup$

I was able to figure it out. In case anyone (mans in ECE 406) 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 Apr 9 at 12:18

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965

$endgroup$

add a comment | 

7

$begingroup$

I was able to figure it out. In case anyone (mans in ECE 406) 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 Apr 9 at 12:18

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965

$endgroup$

add a comment | 

$begingroup$

I was able to figure it out. In case anyone (mans in ECE 406) 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 Apr 9 at 12:18

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965

$endgroup$

share|cite|improve this answer

edited Apr 9 at 12:18

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965

answered Apr 6 at 20:05

Ankit BahlAnkit Bahl

965