0
$\begingroup$

$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.

Following inclusions are known: $$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\oplus\mathsf{L}\subseteq\mathsf{P}$$ $$\mathsf{PP}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^0$$ $$\mathsf{DeterminantMod2}\in\oplus\mathsf{L}$$ where $\mathsf{C}\in\{\mathsf{P},\mathsf{LOGSPACE},\mathsf{DLOGTIME}\}$ and where $\mathsf{DeterminantMod2}$ is the problem of finding determinant of a $0/1$ square matrix modulo $2$.

It is possible $\mathsf{Permanent}$ could reduce to $\mathsf{P}$ by reduction via problems in $\mathsf{DeterminantMod2}$.

So how bad of collapse can we prove to avoid so far?

Is it known

  1. $$\mathsf{CH}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^{{0}^{^{^{\mathsf{C'uniform}\mbox{ -}\oplus\mathsf{L}}}}}$$ and/or
  2. $$\mathsf{CH}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{ACC}^{{0}^{^{^{\mathsf{C'uniform}\mbox{ -}\mathsf{NC}^1}}}}$$ for any $\mathsf{C'}\in\{\mathsf{P},\mathsf{LOGSPACE},\mathsf{DLOGTIME}\}$?

In other words is it known there cannot be a $\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{ACC}^0$ algorithm utilizing $\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{NC}^1$ oracle which computes the permanent?

It is known http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html provides $$\mathsf{PP}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^{{0}}.$$

It is unknown if $$\mathsf{PP}\not\subseteq\mathsf{LOGSPACEuniform}\mbox{ -}\mathsf{TC}^{{0}}$$ holds (What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?).

Possibility of 2. is the deeper collapse.

Update The comments below indicate following collapse is not ruled out: $$\mathsf{CH}\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{ACC}^0.$$

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Any way I look at it, DLOGTIME-uniform $\mathrm{TC}^0$ with a $C'$-uniform $\oplus L$ (whatever that is supposed to mean; normally, $\oplus L$ is already a uniform class) oracle equals just $C'$-uniform $\oplus L$, and likewise, DLOGTIME-uniform $\mathrm{ACC}^0$ with a $C'$-uniform $\mathrm{NC}^1$ oracle equals $C'$-uniform $\mathrm{NC}^1$. Thus, no such thing has been proven. We don’t even know that PP is not included in DLOGTIME-uniform $\mathrm{NC}^1$. $\endgroup$ – Emil Jeřábek Feb 4 at 9:33
  • $\begingroup$ $ACC$ is similar to ModPH and TC similar to CH. Perhaps Allender's DLOGTIME uniform TC0 not containing PP is time and space hierarchy in disguise? Perhaps similar strategy works to separate DLOGTIME uniform ACC from ModPH? $\endgroup$ – 1.. Feb 4 at 9:51
  • 3
    $\begingroup$ There is no disguise; this is a transparent application of the time hierarchy theorem coupled with a padding argument. $\endgroup$ – Emil Jeřábek Feb 4 at 10:08
  • $\begingroup$ @EmilJeřábek Why Allender's proof fails for separating the class $\mathsf{PP}$ and either of the classes $\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$ or $\mathsf{Puniform}\mbox{-}\mathsf{TC}^0$ but works for separating the class $\mathsf{PP}$ and the class $\mathsf{DLOGTIMEuniform}\mbox{-}\mathsf{TC}^0$? Is there something about $\mathsf{LOGSPACEuniform}$ model? $\endgroup$ – 1.. Feb 5 at 2:25
  • 1
    $\begingroup$ I don’t know. It would be quite messy to define. First, LOGSPACE-uniform (P-uniform) TC^0 is, in other words, uniform TC^0 with a polynomial-size LOGSPACE-computable (P-computable, resp.) advice. The exponential version of that, that would make the padding argument work, would be CH with PSPACE-computable (EXP-computable, resp.) exponential-size advice string (accessed by the CH algorithm in a similar way as an oracle). However, as stated, this is not a useful model, as it is too strong: it simply coincides with PSPACE (EXP, resp.), as the advice string may just include the whole truth table. $\endgroup$ – Emil Jeřábek Feb 5 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.