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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Erfüllbarkeitsproblem für Schaltkreise (de)
- Circuit satisfiability problem (en)
- Problème de satisfiabilité de circuit (fr)
- Problema da satisfatibilidade de circuito (pt)
|
| rdfs:comment
| - 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. (de)
- 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. (pt)
- 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. (en)
- 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. (fr)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - 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 . (en)
- 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. (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 . (fr)
- 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. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
