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


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.

| cite | improve this answer | |
  • $\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$ – T.... Dec 28 '17 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$ – T.... Dec 28 '17 at 10:07
  • $\begingroup$ @777 probably best to post that as a separate question or two. $\endgroup$ – Bjørn Kjos-Hanssen Dec 28 '17 at 23:11
  • $\begingroup$ @BjornKjosHanssen done. $\endgroup$ – T.... Dec 28 '17 at 23:20

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.