<p><span class="math-container">$\mathsf{TC}^0$</span> is a small class with <span class="math-container">$\oplus\mathsf{L}$</span> containing it.</p>
<p>Following inclusions are known:
<span class="math-container">$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\oplus\mathsf{L}\subseteq\mathsf{P}$$</span>
<span class="math-container">$$\mathsf{PP}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^0$$</span>
<span class="math-container">$$\mathsf{DeterminantMod2}\in\oplus\mathsf{L}$$</span>
where <span class="math-container">$\mathsf{C}\in\{\mathsf{P},\mathsf{LOGSPACE},\mathsf{DLOGTIME}\}$</span> and where <span class="math-container">$\mathsf{DeterminantMod2}$</span> is the problem of finding determinant of a <span class="math-container">$0/1$</span> square matrix modulo <span class="math-container">$2$</span>.</p>
<p>It is possible <span class="math-container">$\mathsf{Permanent}$</span> could reduce to <span class="math-container">$\mathsf{P}$</span> by reduction via problems in <span class="math-container">$\mathsf{DeterminantMod2}$</span>.</p>
<p>So how bad of collapse can we prove to avoid so far?</p>
<blockquote>
<p>Is it known</p>
<ol>
<li><span class="math-container">$$\mathsf{CH}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^{{0}^{^{^{\mathsf{C'uniform}\mbox{ -}\oplus\mathsf{L}}}}}$$</span>
and/or</li>
<li><span class="math-container">$$\mathsf{CH}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{ACC}^{{0}^{^{^{\mathsf{C'uniform}\mbox{ -}\mathsf{NC}^1}}}}$$</span>
for any <span class="math-container">$\mathsf{C'}\in\{\mathsf{P},\mathsf{LOGSPACE},\mathsf{DLOGTIME}\}$</span>?</li>
</ol>
</blockquote>
<p>In other words is it known there cannot be a <span class="math-container">$\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{ACC}^0$</span> algorithm utilizing <span class="math-container">$\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{NC}^1$</span> oracle which computes the permanent?</p>
<p>It is known <a href="http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html" rel="nofollow noreferrer">http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html</a> provides
<span class="math-container">$$\mathsf{PP}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^{{0}}.$$</span></p>
<p>It is unknown if
<span class="math-container">$$\mathsf{PP}\not\subseteq\mathsf{LOGSPACEuniform}\mbox{ -}\mathsf{TC}^{{0}}$$</span>
holds (<a href="https://cstheory.stackexchange.com/questions/32198/what-is-largest-class-of-functions-c-such-that-we-know-p-in-not-contained">What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?</a>).</p>
<p>Possibility of 2. is the deeper collapse.</p>
<p><strong>Update</strong> The comments below indicate following collapse is not ruled out:
<span class="math-container">$$\mathsf{CH}\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{ACC}^0.$$</span></p>

CC BY-SA 4.0
2021-02-04T09:33:57.167Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-04T09:51:14.067Z
$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?
Turbo
CC BY-SA 4.0
2021-02-04T10:08:47.793Z
There is no disguise; this is a transparent application of the time hierarchy theorem coupled with a padding argument.
Emil Jeřábek
CC BY-SA 4.0
2021-02-05T02:25:47.623Z
@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?
Turbo
CC BY-SA 4.0
2021-02-05T07:56:21.770Z
Why don't you read the proof? The point is that CH is the exponentially scaled up version of DLOGTIME-uniform TC^0, not of any less uniform class.
Emil Jeřábek
CC BY-SA 4.0
2021-02-05T08:20:17.603Z
I see might I ask if there is an exponentially scaled up version of $\mathsf{Cuniform}\mbox{-}\mathsf{TC}^0$ class where $\mathsf{C}\in\{\mathsf{LOGSPACE},\mathsf{P}\}$? Would it be similar $\mathsf{PSPACEuniform}\mbox{-}\mathsf{CH}$ or $\mathsf{EXPuniform}\mbox{-}\mathsf{CH}$ and the $\mathsf{CH}$ which $\mathsf{DLOGTIMEuniform}\mbox{-}\mathsf{TC}^0$ scales be $\mathsf{Puniform}\mbox{-}\mathsf{CH}$ which is the $\mathsf{CH}$ Allender's separation proof refers to?
Turbo
CC BY-SA 4.0
2021-02-05T11:06:49.273Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-02-05T11:19:36.973Z
@EmilJeřábek I think it clarifies a lot and no wonder no one has been smart enough to separate $\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$ and $\mathsf{PP}$ or brave enough to claim these are identical. So the interesting problem here is if $\mathsf{DLOGTIMEuniform}\mbox{-}\mathsf{NC}^1\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$?
Turbo
CC BY-SA 4.0
2021-02-05T11:25:49.093Z
It is not out of the unknown if a 'typical' $\mathsf{NC}^1$ polynomial sized program can be unraveled to a polynomial sized constant depth program having majority gates (the program itself might require $\mathsf{LOGSPACE}$ to construct which is not out of the question since no one knows if $\mathsf{SAT}\not\in\mathsf{TISP}\Big(O\Big(\frac{n^2}{\log n}\Big)\mbox{ time},O(\log n)\mbox{ space}\Big)$). It agrees to $\mathsf{TISP}\Big(\mathsf{poly}(n)\mbox{ time},O(\mathsf{polylog}(n))\mbox{ space}\Big)\not\subseteq\mathsf{DLOGTIME}$ and $\mathsf{P}\not\subseteq\mathsf{DLOGTIME}$).
Turbo
CC BY-SA 4.0
2021-02-05T12:27:12.557Z
$$\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{NC}^1\not\subseteq\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{TC}^0$$ are among the smallest 'difficult' unknown (but extremely helpful (the possibility of non-inclusion is valid under extreme collapse of $\mathsf{CH}$ to $\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$ happens (difficult because proof exists under extreme situations alone is possible))) while

$$\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{NC}^1\not\subseteq\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{TC}^0\not\subseteq\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{ACC}^0$$
is probably 'easier'.
Turbo
<cc.complexity-theory><complexity-classes><polynomial-time><logspace><uniformity>
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
Turbo
# $\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?

(Asked by: username_0 on 2021-02-04)

$\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$?](https://cstheory.stackexchange.com/questions/32198/what-is-largest-class-of-functions-c-such-that-we-know-p-in-not-contained)).

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.$$

**Tags:** cc.complexity-theory, complexity-classes, polynomial-time, logspace, uniformity

> **Comments:**
> **username_1**: 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$.  
> **username_0**: $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?  
> **username_1**: There is no disguise; this is a transparent application of the time hierarchy theorem coupled with a padding argument.  
> **username_0**: @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?  
> **username_1**: Why don't you read the proof? The point is that CH is the exponentially scaled up version of DLOGTIME-uniform TC^0, not of any less uniform class.  
> **username_0**: I see might I ask if there is an exponentially scaled up version of $\mathsf{Cuniform}\mbox{-}\mathsf{TC}^0$ class where $\mathsf{C}\in\{\mathsf{LOGSPACE},\mathsf{P}\}$? Would it be similar $\mathsf{PSPACEuniform}\mbox{-}\mathsf{CH}$ or $\mathsf{EXPuniform}\mbox{-}\mathsf{CH}$ and the $\mathsf{CH}$ which $\mathsf{DLOGTIMEuniform}\mbox{-}\mathsf{TC}^0$ scales be $\mathsf{Puniform}\mbox{-}\mathsf{CH}$ which is the $\mathsf{CH}$ Allender's separation proof refers to?  
> **username_1**: 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.  
> **username_0**: @EmilJeřábek I think it clarifies a lot and no wonder no one has been smart enough to separate $\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$ and $\mathsf{PP}$ or brave enough to claim these are identical. So the interesting problem here is if $\mathsf{DLOGTIMEuniform}\mbox{-}\mathsf{NC}^1\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$?  
> **username_0**: It is not out of the unknown if a 'typical' $\mathsf{NC}^1$ polynomial sized program can be unraveled to a polynomial sized constant depth program having majority gates (the program itself might require $\mathsf{LOGSPACE}$ to construct which is not out of the question since no one knows if $\mathsf{SAT}\not\in\mathsf{TISP}\Big(O\Big(\frac{n^2}{\log n}\Big)\mbox{ time},O(\log n)\mbox{ space}\Big)$). It agrees to $\mathsf{TISP}\Big(\mathsf{poly}(n)\mbox{ time},O(\mathsf{polylog}(n))\mbox{ space}\Big)\not\subseteq\mathsf{DLOGTIME}$ and $\mathsf{P}\not\subseteq\mathsf{DLOGTIME}$).  
> **username_0**: $$\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{NC}^1\not\subseteq\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{TC}^0$$ are among the smallest 'difficult' unknown (but extremely helpful (the possibility of non-inclusion is valid under extreme collapse of $\mathsf{CH}$ to $\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0$ happens (difficult because proof exists under extreme situations alone is possible))) while  $$\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{NC}^1\not\subseteq\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{TC}^0\not\subseteq\mathsf{LOGTIMEuniform}\mbox{-}\mathsf{ACC}^0$$ is probably 'easier'.  

---

## 0 answers

