1
$\begingroup$

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight generalizations of these three "classes of classes" (nondeterministic, deterministic, probabilistic) like EXPTIME.

This, to us, begged the question:

Suppose you have a class of languages $C\supseteq P$, what are neccessary (and sufficient?) conditions for $C$ to be closed under karp reduction?


Terminology:

  • A language $A$ is karp-reducible to another language $B$, written $A\leq_m B$ iff $\exists $deterministic poly-time turing machine $K_{A,B}:\forall x\in\{0,1\}^*: x\in A\iff K_{A,B}(x)\in B$ holds.
  • A class $C$ is closed under $\leq_m$ iff $\forall B,A\subseteq \{0,1\}^*: B\in C\land A\leq_m B\implies A\in C$ holds.
$\endgroup$
  • 1
    $\begingroup$ I don't think you're going to find a statement of necessary and sufficient conditions that are nicer or easier to understand than "it is closed under Karp reduction". Did you have some kind of space of allowable conditions to narrow this down? Did you have a motivation for asking that might help us give you something more useful? $\endgroup$ – D.W. Nov 5 '19 at 18:11
  • $\begingroup$ @D.W. the main motivation is to have a general statement for various generalizations of P to "have an assurance" that this patterns doesn't break down if you suddenly have "too much computational power / space" or to maybe cover extensions of P beyond "probabilistic, deterministic and non-deterministic". For this I'm essentially interested in "sensible" extensions of P and not so much in "P with some really obscure other language that somehow breaks this" (e.g. not P $\cup$ {some language in EXPTIME that has some other non-P language that is reducible to it}) $\endgroup$ – SEJPM Nov 5 '19 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.