|
gptkbp:instanceOf
|
theoretical computer science
|
|
gptkbp:application
|
gptkb:artificial_intelligence
automated theorem proving
software verification
hardware verification
constraint satisfaction
|
|
gptkbp:complexity
|
NP-complete
|
|
gptkbp:describes
|
whether a Boolean formula can be made true by some assignment of truth values
|
|
gptkbp:encodes
|
conjunctive normal form (CNF)
|
|
gptkbp:field
|
gptkb:logic
computer science
theoretical computer science
|
|
gptkbp:firstBook
|
NP-complete problem
|
|
gptkbp:generalizes
|
gptkb:QBF_(Quantified_Boolean_Formula)
|
|
gptkbp:has_open_question
|
gptkb:P_vs_NP
|
|
gptkbp:hasSpecialCase
|
gptkb:2-SAT
gptkb:Horn-SAT
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Satisfiability (SAT)
|
|
gptkbp:input
|
Boolean formula
|
|
gptkbp:introduced
|
gptkb:Stephen_Cook
gptkb:Cook–Levin_theorem
gptkb:Leonid_Levin
|
|
gptkbp:introducedIn
|
1971
|
|
gptkbp:output
|
satisfiable or unsatisfiable
|
|
gptkbp:related_problem
|
gptkb:MAX-SAT
gptkb:QSAT
gptkb:SAT_modulo_theories_(SMT)
gptkb:UNSAT
|
|
gptkbp:relatedTo
|
gptkb:algebra
gptkb:logic
gptkb:P_vs_NP_problem
gptkb:constraint_satisfaction_problem_(CSP)
|
|
gptkbp:solvable_in_polynomial_time
|
gptkb:2-SAT
|
|
gptkbp:solvedBy
|
gptkb:CDCL_algorithm
gptkb:DPLL_algorithm
Boolean satisfiability problem
|
|
gptkbp:unsolved_in_polynomial_time
|
gptkb:3-SAT
|
|
gptkbp:used_in
|
combinatorial optimization
crypt
planning
bioinformatics
circuit design
model checking
scheduling
software testing
|
|
gptkbp:variant
|
gptkb:3-SAT
gptkb:2-SAT
gptkb:k-SAT
|
|
gptkbp:bfsParent
|
gptkb:Karp's_21_NP-complete_problems
|
|
gptkbp:bfsLayer
|
6
|