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

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

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n4http://dbpedia.org/resource/File:
n9https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
n20http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Light_Up_(puzzle)
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Circuit_SAT
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
dbo:wikiPageRedirects
dbr:Circuit_satisfiability_problem
Subject Item
dbr:PLS_(complexity)
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:List_of_NP-complete_problems
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Boolean_satisfiability_algorithm_heuristics
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Planar_SAT
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Circuit_satisfiability_problem
rdf:type
yago:Problem114410605 yago:Condition113920835 yago:State100024720 yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Difficulty114408086 dbo:Disease yago:WikicatComputationalProblems yago:Attribute100024264
rdfs:label
Problema da satisfatibilidade de circuito Circuit satisfiability problem Problème de satisfiabilité de circuit Erfüllbarkeitsproblem für Schaltkreise
rdfs:comment
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. 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. 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. 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.
foaf:depiction
n20:CircuitSAT.svg
dct:subject
dbc:NP-complete_problems dbc:Computational_problems dbc:Computability_theory
dbo:wikiPageID
34599223
dbo:wikiPageRevisionID
1121533454
dbo:wikiPageWikiLink
dbr:Reduction_(complexity) dbr:Circuit_Value_Problem n4:CircuitSAT.svg dbc:NP-complete_problems dbr:Satisfiability_problem dbr:NOR_gate dbr:Cook–Levin_theorem dbr:NAND_gate dbr:Tseytin_transformation dbc:Computational_problems dbr:Sheffer_stroke dbr:Minesweeper_(video_game) dbc:Computability_theory dbr:Theoretical_computer_science dbr:Conjunctive_normal_form dbr:Functional_completeness dbr:3SAT dbr:Boolean_circuit dbr:NP-hardness dbr:Co-NP-complete dbr:Planar_graph dbr:NP-complete dbr:Decision_problem dbr:Boolean_satisfiability_problem dbr:Netlist
owl:sameAs
n9:4hpRY wikidata:Q5121622 dbpedia-fr:Problème_de_satisfiabilité_de_circuit freebase:m.0j256g8 dbpedia-pt:Problema_da_satisfatibilidade_de_circuito dbpedia-de:Erfüllbarkeitsproblem_für_Schaltkreise yago-res:Circuit_satisfiability_problem
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Main
dbo:thumbnail
n20:CircuitSAT.svg?width=300
dbo: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 . 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. 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 . 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.
gold:hypernym
dbr:Problem
prov:wasDerivedFrom
wikipedia-en:Circuit_satisfiability_problem?oldid=1121533454&ns=0
dbo:wikiPageLength
8679
foaf:isPrimaryTopicOf
wikipedia-en:Circuit_satisfiability_problem
Subject Item
dbr:Minesweeper_(video_game)
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:CSAT
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Non-interactive_zero-knowledge_proof
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Circuit-SAT
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
dbo:wikiPageRedirects
dbr:Circuit_satisfiability_problem
Subject Item
dbr:CircuitSAT
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
dbo:wikiPageRedirects
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Circuit_satisfaction_problem
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
dbo:wikiPageRedirects
dbr:Circuit_satisfiability_problem
Subject Item
dbr:Circuit_satisfiability
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
dbo:wikiPageRedirects
dbr:Circuit_satisfiability_problem
Subject Item
dbr:CIRCUIT-SAT
dbo:wikiPageWikiLink
dbr:Circuit_satisfiability_problem
dbo:wikiPageRedirects
dbr:Circuit_satisfiability_problem
Subject Item
wikipedia-en:Circuit_satisfiability_problem
foaf:primaryTopic
dbr:Circuit_satisfiability_problem