On the Complexity of Worst Case and Expected Time in a Circuit

摘要

The computational delay of a circuit can be described by the natural concept of time [Jakoby et al. STOC94]. We show that for a given input x and circuit C the computation of time_C (x) is P-complete. Moreover, we show that it is NP-complete to decide whether there exists an input x such that time_C(x)<=t for a given time bound t.