Circuit complexity (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (ca) 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) 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. (it) 回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。 (ja) 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 . (pt) 电路复杂性理论在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的前景表示不乐观。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Three_input_Boolean_circuit.jpg?width=300 |
| dbo:wikiPageExternalLink | http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ http://www.cs.tau.ac.il/~zwick/scribe-boolean.html |
| dbo:wikiPageID | 7641969 (xsd:integer) |
| dbo:wikiPageLength | 20342 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1086836071 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Electronic_Colloquium_on_Computational_Complexity dbr:NP_(complexity) dbr:DLOGTIME dbr:Derandomization dbr:Ryan_Williams_(computer_scientist) dbr:NOT_gate dbr:OR_gate dbr:Turing_machine_equivalents dbr:Claude_Shannon dbr:Clique_problem dbr:NC_(complexity) dbr:Machine_that_always_halts dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:Computational_resource dbr:P_(complexity) dbr:Parity_function dbr:Theoretical_computer_science dbr:P/poly dbr:B._G._Teubner_Verlag dbr:Circuit_minimization dbr:Alexander_Razborov dbr:PP_(complexity) dbr:Formal_language dbr:AC0 dbr:ACC0 dbr:AC_(complexity) dbr:AND_gate dbc:Circuit_complexity dbc:Computational_complexity_theory dbr:Abstract_machine dbr:Johan_Håstad dbr:Bit dbr:TC0 dbr:Recursive_language dbr:Directed_acyclic_graph dbr:Average-case_complexity dbr:Boolean_circuit dbr:Boolean_function dbr:Ran_Raz dbr:MA_(complexity) dbr:Turing_machine dbr:John_Wiley_&_Sons_Ltd. dbr:File:Three_input_Boolean_circuit.jpg dbr:Natural_proof dbr:NC1_(complexity) dbr:S2P_(complexity) dbr:In-degree dbr:Deterministic_Turing_machine dbr:Springer_Verlag dbr:Pierre_McKenzie |
| dbp:b | 2 (xsd:integer) |
| dbp:cs1Dates | y (en) |
| dbp:date | May 2019 (en) |
| dbp:group | "nb" (en) |
| dbp:p | P (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_web dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Su |
| dcterms:subject | dbc:Circuit_complexity dbc:Computational_complexity_theory |
| rdfs:comment | 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. (ca) 回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。 (ja) 电路复杂性理论在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的前景表示不乐观。 (zh) 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) 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. (it) 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 . (pt) |
| rdfs:label | Circuit complexity (en) Complexitat de circuits (ca) Complessità dei circuiti (it) 回路計算量 (ja) Complexidade de circuitos (pt) 电路复杂性 (zh) |
| owl:sameAs | freebase:Circuit complexity wikidata:Circuit complexity dbpedia-ca:Circuit complexity dbpedia-it:Circuit complexity dbpedia-ja:Circuit complexity dbpedia-pt:Circuit complexity dbpedia-zh:Circuit complexity https://global.dbpedia.org/id/8CcA |
| prov:wasDerivedFrom | wikipedia-en:Circuit_complexity?oldid=1086836071&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Three_input_Boolean_circuit.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Circuit_complexity |
| is dbo:wikiPageDisambiguates of | dbr:Circuit |
| is dbo:wikiPageRedirects of | dbr:Uniformity_(complexity) dbr:P-nonuniform dbr:Circuit-depth_complexity dbr:Circuit-size_complexity dbr:Circuit_class dbr:Circuit_lower_bounds dbr:Polynomial-time_uniform dbr:Uniform_circuit_complexity dbr:Uniform_circuit_family dbr:Uniformity_(circuit) dbr:Logspace_uniform dbr:Monotone_circuit |
| is dbo:wikiPageWikiLink of | dbr:Proof_complexity dbr:List_of_computability_and_complexity_topics dbr:András_Hajnal dbr:DLOGTIME dbr:Descriptional_Complexity_of_Formal_Systems dbr:Descriptive_Complexity dbr:Descriptive_complexity_theory dbr:Ingo_Wegener dbr:L/poly dbr:Pseudorandom_generator dbr:Turing_machine_equivalents dbr:Clique_problem dbr:NL_(complexity) dbr:Logic_optimization dbr:Lovász_number dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Parity_function dbr:Majority_function dbr:Sunflower_(mathematics) dbr:TC_(complexity) dbr:Tardos_function dbr:Theoretical_computer_science dbr:P/poly dbr:Avi_Wigderson dbr:BQP dbr:Adder_(electronics) dbr:Fusion_tree dbr:Circuit dbr:Gödel_Prize dbr:Alexander_Razborov dbr:Asymptotic_computational_complexity dbr:James_B._Saxe dbr:AC0 dbr:ACC0 dbr:AC_(complexity) dbr:Advice_(complexity) dbr:Johan_Håstad dbr:Karp–Lipton_theorem dbr:Blue_book dbr:TC0 dbr:Averaging_argument dbr:Boolean_algebra dbr:Boolean_circuit dbr:Boolean_function dbr:Circuit_(computer_science) dbr:Circuits_over_sets_of_natural_numbers dbr:Michael_Sipser dbr:Uniformity_(complexity) dbr:Quantum_circuit dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Lupanov_representation dbr:NP/poly dbr:Natural_proof dbr:Switching_circuit_theory dbr:Semi-membership dbr:P-nonuniform dbr:Circuit-depth_complexity dbr:Circuit-size_complexity dbr:Circuit_class dbr:Circuit_lower_bounds dbr:Polynomial-time_uniform dbr:Uniform_circuit_complexity dbr:Uniform_circuit_family dbr:Uniformity_(circuit) dbr:Logspace_uniform dbr:Monotone_circuit |
| is rdfs:seeAlso of | dbr:Boolean_circuit |
| is foaf:primaryTopic of | wikipedia-en:Circuit_complexity |
