<p>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
<a href="https://link.springer.com/article/10.1007/s00153-013-0351-x" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00153-013-0351-x</a>
for the classic diagram of the seven.</p>

<p>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.</p>

CC BY-SA 3.0
2017-12-28T09:14:15.840Z
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
CC BY-SA 3.0
2017-12-28T10:07:15.230Z
https://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
CC BY-SA 3.0
2017-12-28T23:11:51.540Z
@777 probably best to post that as a separate question or two.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-12-28T23:20:07.920Z
@BjornKjosHanssen done.
Turbo
CC BY-SA 3.0
2017-12-28T08:50:22.530Z
2017-12-28T08:55:27.557Z
2017-12-28T08:55:27.557Z
Bjørn Kjos-Hanssen
<p>What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?</p>

<cc.complexity-theory><reference-request><complexity-classes><reductions><relativization>
What is conjunctive truth table reduction?
Turbo
# What is conjunctive truth table reduction?

(Asked by: username_0 on 2017-12-27)

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

**Tags:** cc.complexity-theory, reference-request, complexity-classes, reductions, relativization

---

## 1 answers

### Answer by username_1 on 2017-12-28. Score: 3 | Accepted 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.

> **Comments:**
> **username_0**: 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)?  
> **username_0**: https://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$?  
> **username_1**: @777 probably best to post that as a separate question or two.  
> **username_0**: @BjornKjosHanssen done.  

---

