circuit value problem

{{Short description|Computational problem}}

File:Combinatorial Logic Example.svg

The circuit value problem (or circuit evaluation problem) is the computational problem of computing the output of a given Boolean circuit on a given input.

The problem is complete for P under uniform AC0 reductions. Note that, in terms of time complexity, it can be solved in linear time simply by a topological sort.

The Boolean formula value problem (or Boolean formula evaluation problem) is the special case of the problem when the circuit is a tree. The Boolean formula value problem is complete for NC (complexity) with respect to AC{{sup|0}} reductions.{{cite conference | url=https://dl.acm.org/doi/pdf/10.1145/28395.28409 | author=Samuel R. Buss | author-link=Samuel Buss | title=The Boolean formula value problem is in ALOGTIME | editor=Alfred V. Aho | editor-link=Alfred Aho| book-title=Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC) | publisher=ACM | pages=123–131 | date=Jan 1987 | doi=10.1145/28395.28409 | url-access=subscription }} ([http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean Author's draft])

The problem is closely related to the Boolean satisfiability problem which is complete for NP and its complement, the propositional tautology problem, which is complete for co-NP.