About: Circuit complexity

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Circuit complexity Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

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 (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly.

Attributes	Values
rdfs:label	Circuit complexity (en)
rdfs:comment	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 (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly. (en)
sameAs	Circuit complexity
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cite_web dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Su
Subject	Circuit complexity Computational complexity theory
Link from a Wikipage to an external page	http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ http://www.cs.tau.ac.il/~zwick/scribe-boolean.html
thumbnail	wiki-commons:Special:FilePath/Three_input_Boolean_circuit.jpg?width=300
foaf:depiction
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Circuit_complexity?oldid=1074473449&ns=0
Wikipage page ID	7641969 (xsd:integer)
page length (characters) of wiki page	20458 (xsd:nonNegativeInteger)
Wikipage revision ID	1074473449 (xsd:integer)
Link from a Wikipage to another Wikipage	Formal language Logic optimization Machine that always halts NC (complexity) NP-completeness OR gate TC0 Wiley (publisher) AC0 ACC0 AC (complexity) AND gate Abstract machine Alexander Razborov Arthur–Merlin protocol Average-case complexity Bibliotheca Teubneriana Bit Boolean circuit Boolean function Turing machine Turing machine equivalents Circuit complexity Computational complexity theory Directed acyclic graph Directed graph P/poly PP (complexity) P (complexity) Claude Shannon DLOGTIME Springer Science+Business Media Time complexity Clique problem Complexity class Algorithmic complexity Computational problem Computational resource Johan Håstad Parity function Electronic Colloquium on Computational Complexity Ryan Williams (computer scientist) S2P (complexity) Inverter (logic gate) Theoretical computer science Natural proof Ran Raz Randomized algorithm Recursive language dbr:Pierre_McKenzie
has abstract	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 (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Circuit_complexity
is rdfs:seeAlso of	Boolean circuit
is Wikipage redirect of	Logspace uniform Circuit-depth complexity Circuit-size complexity Circuit class Circuit lower bounds Monotone circuit P-nonuniform Polynomial-time uniform Uniform circuit complexity Uniform circuit family Uniformity (circuit) Uniformity (complexity)
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures Logic optimization NC (complexity) NL (complexity) NP/poly AC0 ACC0 AC (complexity) Adder (electronics) Advice (complexity) Alexander Razborov András Hajnal Asymptotic computational complexity Averaging argument Avi Wigderson

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (82 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software