Are there any non-trivial functions in TC1? Apart from that are there functions which are known to be in NC2 but not in TC1?


According to wikipedia, topological sorting is in NC2. Note sure whether this is trustworthy, the proposed algorithm seems to require AC2:

One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering (Dekel, Nassimi & Sahni 1981).

To check whether this algorithm is really in NC2 instead of just AC2, note that even so a single addition could take log log n time, all the additions of a max-plus matrix multiplication can be done in parallel. However, it is unclear how to do a single binary max operation in constant time.

It looks as if the max operations of a max-plus matrix multiplication cannot all be done in parallel. Maybe there is some trick to get the max of n numbers with log n bits in log n time, but I cannot see it at the moment. Edit: Here is the trick: Expand the numbers from binary to unary, then the maximum can be computed independent for each bit. Since conversion between unary and binary can be done in AC0 in both directions, it looks like we don't just get NC2, but even AC1. So this is even an example for the real question, i.e. a non-trivial function in TC1.

As Emil Jeřábek pointed out, there is no end to functions in TC1:

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)

However, I have the impression that all those examples are also in AC1 or even weaker classes like SAC1. Just like my example which initially was even unclear whether it is in NC2, they don't need the power of TC1.

Coming up with examples which are in TC1 (or NC2) and really need TC1 (or NC2) will be extremely challenging.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.