| http://dbpedia.org/ontology/abstract
|
In theoretical computer science, the circu … In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1. If that is the case, the circuit is called satisfiable. Otherwise, the circuit is called unsatisfiable. In the figure to the right, the left circuit can be satisfied by setting both inputs to be 1, but the right circuit is unsatisfiable. CircuitSAT is closely related to Boolean satisfiability problem (SAT), and likewise, has been proven to be NP-complete. It is a prototypical NP-complete problem; the Cook–Levin theorem is sometimes proved on CircuitSAT instead of on the SAT, and then CircuitSAT can be reduced to the other satisfiability problems to prove their NP-completeness. The satisfiability of a circuit containing arbitrary binary gates can be decided in time .rary binary gates can be decided in time .
, Na teoria da ciência da computação, o prob … Na teoria da ciência da computação, o problema da satisfatibilidade de circuito (também conhecido como CIRCUITO-SAT, CircuitoSAT, CSAT, etc.) é o problema de decisão de determinar se um dado circuito Booleano tem uma atribuição das entradas, que torna a saída verdadeira.as entradas, que torna a saída verdadeira.
, En informatique théorique, le problème de … En informatique théorique, le problème de satisfaisabilité d'un circuit (aussi connu sous le nom de CIRCUIT-SAT, CircuitSAT, CSAT[réf. nécessaire], etc.) est le problème de décision consistant à déterminer si pour un circuit booléen donné, il existe une affectation de ses entrées qui rende la sortie vraie. En d'autres termes, on demande si les entrées d'un circuit booléen donné peuvent être réglées de manière cohérente sur 1 ou 0 de sorte que le circuit émette 1. Si tel est le cas, le circuit est dit satisfaisable. Sinon, le circuit est dit insatisfaisable. Sur la figure de droite, le circuit de gauche peut être satisfait en définissant les deux entrées sur 1, mais le circuit de droite n'est pas satisfaisable. CIRCUIT-SAT est étroitement lié au problème de satisfiabilité booléenne (SAT) et est NP-complet comme lui. Le théorème de Cook-Levin est parfois prouvé sur CIRCUIT-SAT plutôt que sur SAT, puis réduit aux autres problèmes de satisfiabilité pour prouver leur NP-complétude. La satisfaisabilité d'un circuit contenant portes binaires quelconques peut être décidée en temps .s quelconques peut être décidée en temps .
, In der theoretischen Informatik (insbesond … In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist das Erfüllbarkeitsproblem für Schaltkreise (englisch Circuit Satisfiability Problem, CircuitSAT, CSAT) das Entscheidungsproblem, ob es für eine gegebene boolesche Schaltung eine Eingabe gibt, die den Ausgang wahr macht. Eingabe gibt, die den Ausgang wahr macht.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/CircuitSAT.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageID
|
34599223
|
| http://dbpedia.org/ontology/wikiPageLength
|
8679
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1121533454
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Category:Computability_theory +
, http://dbpedia.org/resource/Netlist +
, http://dbpedia.org/resource/Category:Computational_problems +
, http://dbpedia.org/resource/Conjunctive_normal_form +
, http://dbpedia.org/resource/Tseytin_transformation +
, http://dbpedia.org/resource/Co-NP-complete +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/3SAT +
, http://dbpedia.org/resource/Reduction_%28complexity%29 +
, http://dbpedia.org/resource/Theoretical_computer_science +
, http://dbpedia.org/resource/Cook%E2%80%93Levin_theorem +
, http://dbpedia.org/resource/NAND_gate +
, http://dbpedia.org/resource/Category:NP-complete_problems +
, http://dbpedia.org/resource/NOR_gate +
, http://dbpedia.org/resource/Boolean_circuit +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/NP-hardness +
, http://dbpedia.org/resource/Sheffer_stroke +
, http://dbpedia.org/resource/Boolean_satisfiability_problem +
, http://dbpedia.org/resource/Minesweeper_%28video_game%29 +
, http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Satisfiability_problem +
, http://dbpedia.org/resource/Circuit_Value_Problem +
, http://dbpedia.org/resource/File:CircuitSAT.svg +
, http://dbpedia.org/resource/Functional_completeness +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Main +
, http://dbpedia.org/resource/Template:Reflist +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Computational_problems +
, http://dbpedia.org/resource/Category:Computability_theory +
, http://dbpedia.org/resource/Category:NP-complete_problems +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Problem +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Circuit_satisfiability_problem?oldid=1121533454&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/CircuitSAT.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Circuit_satisfiability_problem +
|
| owl:sameAs |
http://www.wikidata.org/entity/Q5121622 +
, http://dbpedia.org/resource/Circuit_satisfiability_problem +
, http://yago-knowledge.org/resource/Circuit_satisfiability_problem +
, https://global.dbpedia.org/id/4hpRY +
, http://pt.dbpedia.org/resource/Problema_da_satisfatibilidade_de_circuito +
, http://de.dbpedia.org/resource/Erf%C3%BCllbarkeitsproblem_f%C3%BCr_Schaltkreise +
, http://rdf.freebase.com/ns/m.0j256g8 +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_de_satisfiabilit%C3%A9_de_circuit +
|
| rdf:type |
http://dbpedia.org/class/yago/Attribute100024264 +
, http://dbpedia.org/class/yago/State100024720 +
, http://dbpedia.org/class/yago/WikicatNP-completeProblems +
, http://dbpedia.org/class/yago/Problem114410605 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/ontology/Disease +
, http://dbpedia.org/class/yago/Difficulty114408086 +
, http://dbpedia.org/class/yago/WikicatComputationalProblems +
, http://dbpedia.org/class/yago/Condition113920835 +
|
| rdfs:comment |
In der theoretischen Informatik (insbesond … In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist das Erfüllbarkeitsproblem für Schaltkreise (englisch Circuit Satisfiability Problem, CircuitSAT, CSAT) das Entscheidungsproblem, ob es für eine gegebene boolesche Schaltung eine Eingabe gibt, die den Ausgang wahr macht. Eingabe gibt, die den Ausgang wahr macht.
, Na teoria da ciência da computação, o prob … Na teoria da ciência da computação, o problema da satisfatibilidade de circuito (também conhecido como CIRCUITO-SAT, CircuitoSAT, CSAT, etc.) é o problema de decisão de determinar se um dado circuito Booleano tem uma atribuição das entradas, que torna a saída verdadeira.as entradas, que torna a saída verdadeira.
, In theoretical computer science, the circu … In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1. If that is the case, the circuit is called satisfiable. Otherwise, the circuit is called unsatisfiable. In the figure to the right, the left circuit can be satisfied by setting both inputs to be 1, but the right circuit is unsatisfiable.1, but the right circuit is unsatisfiable.
, En informatique théorique, le problème de … En informatique théorique, le problème de satisfaisabilité d'un circuit (aussi connu sous le nom de CIRCUIT-SAT, CircuitSAT, CSAT[réf. nécessaire], etc.) est le problème de décision consistant à déterminer si pour un circuit booléen donné, il existe une affectation de ses entrées qui rende la sortie vraie. En d'autres termes, on demande si les entrées d'un circuit booléen donné peuvent être réglées de manière cohérente sur 1 ou 0 de sorte que le circuit émette 1. Si tel est le cas, le circuit est dit satisfaisable. Sinon, le circuit est dit insatisfaisable. Sur la figure de droite, le circuit de gauche peut être satisfait en définissant les deux entrées sur 1, mais le circuit de droite n'est pas satisfaisable.circuit de droite n'est pas satisfaisable.
|
| rdfs:label |
Problema da satisfatibilidade de circuito
, Problème de satisfiabilité de circuit
, Erfüllbarkeitsproblem für Schaltkreise
, Circuit satisfiability problem
|
