2
$\begingroup$

What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?

$\endgroup$

1 Answer 1

3
$\begingroup$

In the binary case they are two of the seven truth-table reducibilities $$m, btt(1), c, d, p, \ell, tt$$ based on polynomial clones. See Figure 1 in Culver's paper https://link.springer.com/article/10.1007/s00153-013-0351-x for the classic diagram of the seven.

In the ternary case there are uncountably many such reducibilities instead of 7, as Culver demonstrates using a prior result about clones from universal algebra.

$\endgroup$
4
  • $\begingroup$ So only existence/non-existence of $m$ or many one is the only reducibility for proving class inclusions like $NP$ is in/not in $P$ and $tt$ suffices for $coNP$ in $P^{NP}$. What do the others give (other than they give tt)? $\endgroup$
    – Turbo
    Dec 28, 2017 at 9:14
  • $\begingroup$ link.springer.com/content/pdf/10.1007%2Fs00153-013-0351-x.pdf gives $btt(1)$ implies $p$. What does norm $1$ mean? Is there illustrative examples that help understand both from hierarchy between $P$ and $PSPACE$? $\endgroup$
    – Turbo
    Dec 28, 2017 at 10:07
  • $\begingroup$ @777 probably best to post that as a separate question or two. $\endgroup$ Dec 28, 2017 at 23:11
  • $\begingroup$ @BjornKjosHanssen done. $\endgroup$
    – Turbo
    Dec 28, 2017 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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