About: Circuit Value Problem

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

About: Circuit Value Problem Goto Sponge NotDistinct Permalink

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

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 (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 NC1.

Attributes	Values
rdfs:label	Circuit Value Problem (en)
rdfs:comment	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 (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 NC1. (en)
sameAs	Circuit Value Problem
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Sup dbt:Compu-prog-stub
Subject	Computational problems Polynomial-time problems Theoretical computer science
thumbnail	wiki-commons:Special:FilePath/Combinatorial_Logic_Example.svg?width=300
foaf:depiction
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Circuit_Value_Problem?oldid=979254767&ns=0
Wikipage page ID	50036569 (xsd:integer)
page length (characters) of wiki page	1352 (xsd:nonNegativeInteger)
Wikipage revision ID	979254767 (xsd:integer)
Link from a Wikipage to another Wikipage	NC (complexity) NP-completeness AC0 Boolean circuit Boolean satisfiability problem Tautology (logic) Computational problems Polynomial-time problems Theoretical computer science P (complexity) Time complexity Co-NP Topological sorting dbr:Boolean_Formula_Value_Problem
has abstract	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 (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 NC1. 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Circuit_Value_Problem
is Link from a Wikipage to another Wikipage of	Boolean circuit Charitybuzz Circuit satisfiability problem
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Circuit_Value_Problem

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 (71 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