Benutzer:ArneVogel/Circuit Satisfiability Problem

aus Wikipedia, der freien Enzyklopädie
< Benutzer:ArneVogel
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 23. November 2017 um 10:31 Uhr durch imported>ArneVogel(2784176).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

In der theoretischen Informatik ist das Schaltkreis Erfüllbarkeitsproblem (Circuit Satisfiability Problem, CircuitSAT,CSAT) das Entscheidungsproblem, ob eine gegebene boolesche Schaltung eine Zuordnung ihrer Eingänge hat, die den Ausgang wahr macht.[1]

CSAT ist NP-Vollständig.[2]


Einzelnachweise

  1. ↑ http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf
  2. ↑ https://people.eecs.berkeley.edu/~luca/cs170/notes/lecture22.pdf

Siehe auch

Abgerufen von „https://de.wikiup.org/index.php?title=Benutzer:ArneVogel/Circuit_Satisfiability_Problem&oldid=171299706“