# What is conjunctive truth table reduction?

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

## 1 Answer

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.

• 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)? – Turbo Dec 28 '17 at 9:14
• 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$? – Turbo Dec 28 '17 at 10:07
• @777 probably best to post that as a separate question or two. – Bjørn Kjos-Hanssen Dec 28 '17 at 23:11
• @BjornKjosHanssen done. – Turbo Dec 28 '17 at 23:20