<p>Uniform TC1 is known to be in Catalytic Logspace. To improve the lower bound, we are looking for some functions known to be in NC2 but not in TC1.</p>

<p>Also, what are some of the natural functions known in TC1?</p>

CC BY-SA 4.0
2018-07-09T06:01:51.910Z
For the second question, there is no end to it: all context-free languages, determinants over Z and over finite fields, various related problems in linear algebra (matrix powering, matrix inverse, characteristic polynomial, solvability of linear systems).
Emil Jeřábek
CC BY-SA 4.0
2018-07-09T13:20:42.150Z
For your first question the answer is "no", open if NC2 is in TC0, or NP in uniform-TC0 for that matter.
Lance Fortnow
CC BY-SA 4.0
2018-07-10T12:29:51.357Z
@LanceFortnow Thanks. Are there functions which are known to be in NC2 but believed and not known to be in TC1?
Vimal Raj Sharma
CC BY-SA 4.0
2018-07-11T07:04:39.250Z
@ThomasKlimpel The question is about natural/interesting problems, not about complete problems. Of course there are NC^2-complete problems, but they are uninformative ("given a constant $(\log n )^2$-depth circuit, does it evaluate to 1?"). The fact that it's difficult to find such problems is what makes the question interesting, so replacing NC^2 with NC would defeat its purpose.
Emil Jeřábek
<cc.complexity-theory>
Are there any known functions in NC2 but not in TC1?
Vimal Raj Sharma
# Are there any known functions in NC2 but not in TC1?

(Asked by: username_0 on 2018-07-08)

Uniform TC1 is known to be in Catalytic Logspace. To improve the lower bound, we are looking for some functions known to be in NC2 but not in TC1.

Also, what are some of the natural functions known in TC1?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: For the second question, there is no end to it: all context-free languages, determinants over Z and over finite fields, various related problems in linear algebra (matrix powering, matrix inverse, characteristic polynomial, solvability of linear systems).  
> **username_2**: For your first question the answer is "no", open if NC2 is in TC0, or NP in uniform-TC0 for that matter.  
> **username_0**: @LanceFortnow Thanks. Are there functions which are known to be in NC2 but believed and not known to be in TC1?  
> **username_1**: @ThomasKlimpel The question is about natural/interesting problems, not about complete problems. Of course there are NC^2-complete problems, but they are uninformative ("given a constant $(\log n )^2$-depth circuit, does it evaluate to 1?"). The fact that it's difficult to find such problems is what makes the question interesting, so replacing NC^2 with NC would defeat its purpose.  

---

## 0 answers

