Circuit complexity
id:
circuit-complexity-283-12190880
title:
Circuit complexity
text:
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits C 1 , C 2 , … . Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example,
brand slug:
wiki
category slug:
encyclopedia
description:
Model of computational complexity
original url:
https://en.wikipedia.org/wiki/Circuit_complexity
date created:
date modified:
2024-02-28T22:00:29Z
main entity:
{"identifier":"Q1055112","url":"https://www.wikidata.org/entity/Q1055112"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/4/48/Three_input_boolean_circuit.svg","width":728,"height":879}
fields total:
13
integrity:
15