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?

  • 3
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek supports Monica Jul 9 '18 at 6:01
  • 2
    $\begingroup$ For your first question the answer is "no", open if NC2 is in TC0, or NP in uniform-TC0 for that matter. $\endgroup$ – Lance Fortnow Jul 9 '18 at 13:20
  • 1
    $\begingroup$ @LanceFortnow Thanks. Are there functions which are known to be in NC2 but believed and not known to be in TC1? $\endgroup$ – Vimal Raj Sharma Jul 10 '18 at 12:29
  • $\begingroup$ @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. $\endgroup$ – Emil Jeřábek supports Monica Jul 11 '18 at 7:04

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.