This HTML5 document contains 182 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n14http://dbpedia.org/resource/File:
dbpedia-cahttp://ca.dbpedia.org/resource/
n27https://global.dbpedia.org/id/
n20http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/
n18http://dbpedia.org/resource/L/
dbthttp://dbpedia.org/resource/Template:
n22http://dbpedia.org/resource/NP/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
n25http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
n23http://dbpedia.org/resource/P/
n21http://www.cs.tau.ac.il/~zwick/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Proof_complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:András_Hajnal
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:DLOGTIME
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Descriptional_Complexity_of_Formal_Systems
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Descriptive_Complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Descriptive_complexity_theory
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Ingo_Wegener
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
n18:poly
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Pseudorandom_generator
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Turing_machine_equivalents
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Clique_problem
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:NL_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Logic_optimization
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Lovász_number
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Computational_complexity_theory
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:P_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Parity_function
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Majority_function
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Sunflower_(mathematics)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:TC_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Tardos_function
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Theoretical_computer_science
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
n23:poly
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Avi_Wigderson
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:BQP
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Adder_(electronics)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Fusion_tree
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Circuit
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageDisambiguates
dbr:Circuit_complexity
Subject Item
dbr:Gödel_Prize
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Alexander_Razborov
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Asymptotic_computational_complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:James_B._Saxe
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:AC0
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:ACC0
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:AC_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Advice_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Johan_Håstad
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Karp–Lipton_theorem
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Blue_book
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:TC0
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Averaging_argument
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Boolean_algebra
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Boolean_circuit
rdfs:seeAlso
dbr:Circuit_complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Boolean_function
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Circuit_(computer_science)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Circuit_complexity
rdfs:label
电路复杂性 回路計算量 Complexidade de circuitos Complexitat de circuits Complessità dei circuiti Circuit complexity
rdfs:comment
电路复杂性理论在1990年代以前，被众多研究者认为是解决NP与P关系问题的可能的途径之一。电路复杂性研究的对象是非一致性的计算模型，并考虑计算一个布尔函数所需的最小的电路的深度（depth）和大小（size）等资源。其中，大小为多项式大小的电路族可以计算的布尔函数被记为。可以证明，P包含在P/poly之中，而（Karp-Lipton theorem）表明若P/poly在NP之中，则（polynomial hierarchy）将会坍缩至第二层，这是一个不大可能的结果。这两个结果结合起来表明，P/poly可以当作是分离NP与P的一个中间的工具，具体的途径就是证明任一个NP完全问题的电路大小的下界。在直观上说，电路复杂性也绕过了NP与P问题的第一个困难：（relativizing proofs）。 在1980年代，电路复杂性途径取得了一系列的成功，其中包括（Parity function）在中的下界为指数，以及（clique problem）在（monotone circuit）中的下界为指数。然而在1994年和的著名论文（Natural proof）中指出，上面所用证明电路下界的方法，在单向函数存在的前提下是不可能分离NP和P的。该结果使很多专家对证明电路下界来分离NP和P的前景表示不乐观。 No ramo da Ciência da computação teórica, complexidade de circuitos é um ramo da Teoria da complexidade computacional onde Função booleanas são classificadas de acordo com o tamanho ou o grau dos Circuitos booleanos que as computam. Ele trata da complexidade de um circuito Booleano. Uma noção é a complexidade do circuito de uma linguagem recursiva que é decidida por uma família de circuitos (veja mais a seguir). Classe de complexidades definida em termos de circuitos booleanos incluem , , e . 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. 回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。 In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano. Si parla quindi della complessità di un circuito booleano. Una nozione collegata è la complessità dei circuiti di un linguaggio ricorsivo che è deciso da una famiglia di circuiti (vedi sotto). Le classi di complessità definite in termini di circuiti booleani includono AC0, AC, ed NC. La complexitat de circuits és una branca de la teoria de la complexitat en la que les funcions booleanes es classifiquen segons la mida o profunditat del circuit booleà que la computa. Es pot parlar, per tant, de la complexitat d'un circuit booleà. També hi ha el concepte associat de la complexitat d'un circuit d'un llenguatge recursiu que és decidible per una família uniforme de circuits Les classes de complexitat definides en termes de circuits booleans són les classes AC0, AC, TC0 i NC.
foaf:depiction
n25:Three_input_Boolean_circuit.jpg
dct:subject
dbc:Circuit_complexity dbc:Computational_complexity_theory
dbo:wikiPageID
7641969
dbo:wikiPageRevisionID
1086836071
dbo:wikiPageWikiLink
dbr:PP_(complexity) dbr:Ryan_Williams_(computer_scientist) dbr:Directed_acyclic_graph dbr:TC0 dbr:Natural_proof dbr:S2P_(complexity) dbr:Derandomization dbr:DLOGTIME dbr:Formal_language dbr:Bit dbr:AND_gate dbr:In-degree dbr:Turing_machine_equivalents dbr:AC_(complexity) dbr:Ran_Raz n14:Three_input_Boolean_circuit.jpg dbr:Machine_that_always_halts dbr:NC1_(complexity) dbc:Circuit_complexity dbr:B._G._Teubner_Verlag dbr:Pierre_McKenzie dbr:NOT_gate dbr:NP_(complexity) dbr:P_(complexity) dbr:Clique_problem dbr:ACC0 dbr:Computational_problem dbr:Computational_resource dbr:MA_(complexity) dbc:Computational_complexity_theory dbr:AC0 dbr:Circuit_minimization n23:poly dbr:Electronic_Colloquium_on_Computational_Complexity dbr:Claude_Shannon dbr:Boolean_function dbr:Boolean_circuit dbr:John_Wiley_&_Sons_Ltd. dbr:Parity_function dbr:Springer_Verlag dbr:Johan_Håstad dbr:Computational_complexity_theory dbr:Turing_machine dbr:Recursive_language dbr:OR_gate dbr:Deterministic_Turing_machine dbr:Average-case_complexity dbr:Abstract_machine dbr:NC_(complexity) dbr:Theoretical_computer_science dbr:Complexity_class dbr:Alexander_Razborov
dbo:wikiPageExternalLink
n20: n21:scribe-boolean.html
owl:sameAs
dbpedia-it:Complessità_dei_circuiti dbpedia-ca:Complexitat_de_circuits freebase:m.0267lqh wikidata:Q1055112 dbpedia-ja:回路計算量 dbpedia-zh:电路复杂性 dbpedia-pt:Complexidade_de_circuitos n27:8CcA
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Use_dmy_dates dbt:Reflist dbt:Su dbt:Cite_web dbt:Cite_book
dbo:thumbnail
n25:Three_input_Boolean_circuit.jpg?width=300
dbp:b
2
dbp:cs1Dates
y
dbp:date
May 2019
dbp:group
"nb"
dbp:p
P
dbo:abstract
电路复杂性理论在1990年代以前，被众多研究者认为是解决NP与P关系问题的可能的途径之一。电路复杂性研究的对象是非一致性的计算模型，并考虑计算一个布尔函数所需的最小的电路的深度（depth）和大小（size）等资源。其中，大小为多项式大小的电路族可以计算的布尔函数被记为。可以证明，P包含在P/poly之中，而（Karp-Lipton theorem）表明若P/poly在NP之中，则（polynomial hierarchy）将会坍缩至第二层，这是一个不大可能的结果。这两个结果结合起来表明，P/poly可以当作是分离NP与P的一个中间的工具，具体的途径就是证明任一个NP完全问题的电路大小的下界。在直观上说，电路复杂性也绕过了NP与P问题的第一个困难：（relativizing proofs）。 在1980年代，电路复杂性途径取得了一系列的成功，其中包括（Parity function）在中的下界为指数，以及（clique problem）在（monotone circuit）中的下界为指数。然而在1994年和的著名论文（Natural proof）中指出，上面所用证明电路下界的方法，在单向函数存在的前提下是不可能分离NP和P的。该结果使很多专家对证明电路下界来分离NP和P的前景表示不乐观。 回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。 In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano. Si parla quindi della complessità di un circuito booleano. Una nozione collegata è la complessità dei circuiti di un linguaggio ricorsivo che è deciso da una famiglia di circuiti (vedi sotto). Un circuito booleano con bit di input è un grafo aciclico diretto nel quale ogni nodo (solitamente chiamato porta in questo contesto) è o un nodo di input di 0 etichettato da uno degli bit dell'input, una porta AND, una porta OR o una porta NOT. Una di queste porte è designata come la porta dell'output. Tale circuito computa naturalmente una funzione dei suoi input. La dimensione di un circuito è il numero di porte che contiene e la sua profondità è la lunghezza massima di un cammino da una porta di input alla porta di output. Ci sono due nozioni principali di complessità dei circuiti (queste sono delineate in Sipser (1997):324). La complessità della dimensione dei circuiti di una funzione booleana è la dimensione minimale di qualsiasi circuito che computi . La complessità della profondità dei circuiti di una funzione booleana è la profondità minimale di qualsiasi circuito che computi . Queste nozioni si generalizzano quando si consideri la complessità dei circuiti di un linguaggio ricorsivo: un linguaggio formale può contenere stringhe con molte lunghezze diverse di bit. I circuiti booleani, tuttavia, comsentono soltanto un numero fisso di bit degli input. Perciò nessun circuito booleano singolo è capace di decidere tale linguaggio. Per tenere conto di tale possibilità, si considerano famiglie di circuiti dove ciascun accetta input di dimensione . Ciascuna famiglia di circuiti genererà naturalmente un linguaggio ricorsivo producendo quando una stringa è una componente della famiglia, e altrimenti. Diciamo che una famiglia di circuiti è di dimensione minimale se non c'è nessun'altra famiglia che decide su input di qualsiasi dimensione, , con un circuito di dimensione minore di (rispettivamente per le famiglie di profondità minimale). Quindi, la complessità della dimensione dei circuiti di un linguaggio ricorsivo è definita come la funzione , che collega una lunghezza di bit di un input, , alla complessità della dimensione dei circuiti del circuito minimale che decide se gli input di quella lunghezza sono in . La complessità della profondità dei circuiti è definita in modo simile. Le classi di complessità definite in termini di circuiti booleani includono AC0, AC, ed NC. No ramo da Ciência da computação teórica, complexidade de circuitos é um ramo da Teoria da complexidade computacional onde Função booleanas são classificadas de acordo com o tamanho ou o grau dos Circuitos booleanos que as computam. Ele trata da complexidade de um circuito Booleano. Uma noção é a complexidade do circuito de uma linguagem recursiva que é decidida por uma família de circuitos (veja mais a seguir). Um circuito booleano com bits de entrada é um grafo acíclico dirigido onde cada nó (normalmente chamados de porta neste contexto) é um desses quatro elementos: um nó de entrada cujo grau de entrada é 0 representado por um dos bits de entrada, uma porta AND, uma porta OR ou uma porta NOT. Uma dessas portas é designada porta de saída. Tal circuito naturalmente computa uma função a partir de suas entradas. O tamanho de um circuito é o numero de portas que ele contém seu grau é definido pelo comprimento do maior caminho de uma porta de entrada até uma porta de saída. Existem dois conceitos principais da complexidade de circuitos (esses dois conceitos são definidos no Sipser (1997)). A complexidade do tamanho do circuito de uma função Booleana é o tamanho mínimo de qualquer circuito que compute . A complexidade do grau do circuito de uma função Booleana é o grau mínimo de qualquer circuito que compute . Essas noções também se aplicam quando se considera a complexidade do circuito de uma linguagem recursiva: Uma linguagem formal pode conter muitas palavras com uma quantidade diversa de bits por palavra. Circuitos booleanos, no entanto, só permitem um número fixo de bits por entrada. Logo, nenhum circuito booleano é capaz de decidir sozinho uma linguagem recursiva. Para permitir que isso seja feito, deve-se considerar famílias de circuitos onde cada aceita entradas de tamanho . Cada família de circuito vai naturalmente gerar uma linguagem recursiva ao dar como saída quando uma palavra for membro da família, e caso contrário. Dizemos que uma família de circuitos tem tamanho mínimo se não existe outra família que decida com um circuito menor do que o tamanho de , para entradas de tamanho . O mesmo se aplica para famílias de grau mínimo. Sendo assim, a complexidade do tamanho do circuito de uma linguagem recursiva é definia como a função , que relaciona o tamanho dos bits de uma entrada, , com a complexidade do tamanho de um circuito mínimo que decide se entradas desse tamanho estão em . A complexidade do grau do circuito é definida similarmente. Classe de complexidades definida em termos de circuitos booleanos incluem , , e . 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. La complexitat de circuits és una branca de la teoria de la complexitat en la que les funcions booleanes es classifiquen segons la mida o profunditat del circuit booleà que la computa. Es pot parlar, per tant, de la complexitat d'un circuit booleà. També hi ha el concepte associat de la complexitat d'un circuit d'un llenguatge recursiu que és decidible per una família uniforme de circuits Les classes de complexitat definides en termes de circuits booleans són les classes AC0, AC, TC0 i NC.
prov:wasDerivedFrom
wikipedia-en:Circuit_complexity?oldid=1086836071&ns=0
dbo:wikiPageLength
20342
foaf:isPrimaryTopicOf
wikipedia-en:Circuit_complexity
Subject Item
dbr:Circuits_over_sets_of_natural_numbers
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Michael_Sipser
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Uniformity_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Quantum_circuit
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Lupanov_representation
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
n22:poly
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Natural_proof
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Switching_circuit_theory
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:Semi-membership
dbo:wikiPageWikiLink
dbr:Circuit_complexity
Subject Item
dbr:P-nonuniform
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Circuit-depth_complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Circuit-size_complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Circuit_class
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Circuit_lower_bounds
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Polynomial-time_uniform
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Uniform_circuit_complexity
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Uniform_circuit_family
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Uniformity_(circuit)
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Logspace_uniform
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
dbr:Monotone_circuit
dbo:wikiPageWikiLink
dbr:Circuit_complexity
dbo:wikiPageRedirects
dbr:Circuit_complexity
Subject Item
wikipedia-en:Circuit_complexity
foaf:primaryTopic
dbr:Circuit_complexity