What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\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$– TurboDec 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$– TurboDec 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
-