1
$\begingroup$

I have a reduction and can't understand if it is Karp reduction. I want understand if my reduction is Karp reduction as well as understand how to determine which one is so.

Let I have formula $\Phi = (l_{1,1}\lor l_{1,2}\lor...\lor l_{1,k_1})\land(l_{2,1}\lor...\lor l_{2,k_2})\land...\land(l_{n,1}\lor...\lor l_{n,k_n})$

And I want to check if it is minimal CNF (decision variant of CNF minimization, one that requires to minimize amount of literal occurences). Determine if formula has an equivalent with $m$ or lower amount of literal occurences. This problem is $\Sigma^P_2$-complete. However, I have reduction:

$$Min(\Phi)=m\ge(length(\Phi)-(\overline{S(\Phi\land\overline {l_{1,1}}\land l_{1,2}\land...\land l_{1,k_1})}+\overline{S(\Phi\land l_{1,1}\land \overline{l_{1,2}}\land...\land l_{1,k_1})}+...+\overline{S(\Phi\land l_{1,1}\land l_{1,2}\land...\land\overline{l_{1,k_1}})}+\overline{S(\Phi\land\overline {l_{2,1}}\land...\land l_{2,k_2})}+...+\overline{S(\Phi\land l_{2,1}\land...\land\overline{l_{2,k_2}})}+...+\overline{S(\Phi\land\overline {l_{n,1}}\land...\land l_{n,k_n})}+...+\overline{S(\Phi\land l_{n,1}\land...\land\overline{l_{n,k_n}})}))$$

Here I use $S$ to denote $SAT$-problem.

$length(\Phi)$ counts amount of literal occurences in formula $\Phi$.

If this reduction is Karp reduction, then $\Delta^P_2 = \Sigma^P_2$ and $PH$ collapses.

But is this reduction Karp reduction, how can I determine it (general method is preferred)?

Okay, it seems, using $P^{NP}$ machine I can use $+,-,<,>,=$ operations (do not know about $\cdot,/$) for any data machine has at some step (after getting answer from oracle). If so, then I'm surprised that no one found such simple algorithm for CNF minimization.

|cite|improve this question
$\endgroup$
  • $\begingroup$ A Karp reduction from $A$ to $B$ is a polytime function $f$ such that $x \in A$ iff $f(x) \in B$. $\endgroup$ – Yuval Filmus Jun 29 '17 at 10:46
  • $\begingroup$ @YuvalFilmus, okay, in my case, $A$ is minimization problem, $B$ is a problem that answers $m\ge$ (length - number of UNSAT answers). Then, $x$ is $\Phi$. What here is $f(x)$? $\endgroup$ – rus9384 Jun 29 '17 at 10:50
  • 1
    $\begingroup$ That's for you to say. Your reduction is a Karp reduction if it can be implemented using a function $f$ which can be computed in polynomial time. I suggest looking at examples of NP-hardness proofs, which also feature the same type of reduction. $\endgroup$ – Yuval Filmus Jun 29 '17 at 10:51
  • $\begingroup$ @YuvalFilmus, I know, for example, that I can't invert the answer on NTM. Thus, reduction $NSAT(\Phi)=SAT(\overline \Phi)$ is not Karp reduction. However, here I use arithmetical operation $+$. Is it restricted for DTM (under Karp reductions) or not? $\endgroup$ – rus9384 Jun 29 '17 at 11:00
  • $\begingroup$ If your reduction collapses PH, then it is safe to say that it isn't a Karp reduction. So you shouldn't be able to express it as a function $f$ satisfying the constraints above. $\endgroup$ – Yuval Filmus Jun 29 '17 at 14:56
2
$\begingroup$

Your reduction repeatedly calls a SAT oracle. Karp reductions only make one oracle call, and furthermore they must immediately return whatever the oracle returns (so it's like a "tail call"). So your reduction isn't a Karp reduction.

How to know if a reduction is a Karp reduction? Use the definition. A Karp reduction from a language $A$ to a language $B$ is a polytime function $f$ such that for all $x$ we have $x \in A$ iff $f(x) \in B$. If your reduction cannot be put in this form, it is not a Karp reduction.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So, I can't use use $NP$ oracle in $P^{NP}$ machine multiple times to show that problem is in $P^{NP}$? $\endgroup$ – rus9384 Jun 29 '17 at 17:23
  • $\begingroup$ Definitely, but this doesn't constitute a Karp reduction. Rather, it is an oracle reduction (also known as a Turing reduction). $\endgroup$ – Yuval Filmus Jun 29 '17 at 17:41
  • $\begingroup$ I know that it's Turing reduction (I think, every reduction is Turing reduction). But it can't prove equality between $P^{NP}$ and $NP^{NP}$, right? However, as the paper says, prime CNF is already in $P^{NP}$ and thus I only need to show that prime CNF can be minimized on $P^{NP}$ or weaker machine. $\endgroup$ – rus9384 Jun 29 '17 at 17:59
  • $\begingroup$ Karp reductions are weaker than Turing reductions. In particular, there is a Turing reduction between the halting problem and its complement, but there is no such Karp reduction (even if you only require $f$ to be computable). $\endgroup$ – Yuval Filmus Jun 29 '17 at 18:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.