SAT
E679891
SAT (the Boolean satisfiability problem) is the fundamental decision problem of determining whether there exists an assignment of truth values that makes a given Boolean formula evaluate to true.
All labels observed (1)
| Label | Occurrences |
|---|---|
| SAT canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7666071 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: SAT Context triple: [NP-completeness, hasCanonicalProblem, SAT]
-
A.
SAT
SAT is Mexico’s federal tax administration authority responsible for collecting taxes, overseeing customs, and enforcing fiscal regulations.
-
B.
SAT
The SAT is a standardized college admissions test widely used in the United States to assess high school students' readiness for undergraduate study.
-
C.
SAT
SAT is the three-letter IATA airport code for San Antonio International Airport, a major commercial airport serving San Antonio, Texas.
-
D.
UP College Admission Test
The UP College Admission Test is a highly competitive standardized exam used to select incoming students for the University of the Philippines, the country’s premier public university system.
-
E.
GRE
GRE is the three-letter International Olympic Committee country code representing Greece in Olympic competitions.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: SAT Target entity description: SAT (the Boolean satisfiability problem) is the fundamental decision problem of determining whether there exists an assignment of truth values that makes a given Boolean formula evaluate to true.
-
A.
SAT
The SAT is a standardized college admissions test widely used in the United States to assess high school students' readiness for undergraduate study.
-
B.
SAT
SAT is Mexico’s federal tax administration authority responsible for collecting taxes, overseeing customs, and enforcing fiscal regulations.
-
C.
SAT
SAT is the three-letter IATA airport code for San Antonio International Airport, a major commercial airport serving San Antonio, Texas.
-
D.
UP College Admission Test
The UP College Admission Test is a highly competitive standardized exam used to select incoming students for the University of the Philippines, the country’s premier public university system.
-
E.
GRE
The GRE (Graduate Record Examination) is a standardized test widely used for admission to graduate and business school programs, assessing verbal reasoning, quantitative reasoning, and analytical writing skills.
- F. None of above. chosen
Statements (59)
| Predicate | Object |
|---|---|
| instanceOf |
computational problem
ⓘ
decision problem ⓘ |
| alsoKnownAs |
Boolean satisfiability problem
NERFINISHED
ⓘ
SAT problem ⓘ |
| canonicalForm | conjunctive normal form ⓘ |
| clauseDefinition | disjunction of literals ⓘ |
| commonAlgorithmicApproach |
CDCL (conflict-driven clause learning)
NERFINISHED
ⓘ
DPLL algorithm NERFINISHED ⓘ local search algorithms ⓘ stochastic search ⓘ |
| complexityClass |
NP
ⓘ
NP-complete ⓘ |
| domain | Boolean formulas over variables with values true or false ⓘ |
| field |
computational complexity theory
ⓘ
mathematical logic ⓘ theoretical computer science ⓘ |
| formalDefinition | Given a Boolean formula, determine whether there exists a truth assignment to its variables that makes the formula evaluate to true ⓘ |
| hasImportantVariant |
#SAT
ⓘ
2-SAT NERFINISHED ⓘ 3-SAT NERFINISHED ⓘ Horn-SAT NERFINISHED ⓘ MAX-SAT NERFINISHED ⓘ k-SAT NERFINISHED ⓘ |
| historicalMilestone | first problem proven NP-complete ⓘ |
| importance |
basis for many reductions in complexity theory
ⓘ
central to the theory of NP-completeness ⓘ |
| input | Boolean formula ⓘ |
| isInClassNPBecause | a satisfying assignment can be verified in polynomial time ⓘ |
| isNPCompleteBecause | every problem in NP can be reduced to SAT in polynomial time ⓘ |
| literalDefinition | variable or its negation ⓘ |
| npCompletenessProofBy |
Leonid Levin
NERFINISHED
ⓘ
Stephen Cook NERFINISHED ⓘ |
| npCompletenessProofPublication | The Complexity of Theorem-Proving Procedures NERFINISHED ⓘ |
| npCompletenessProofYear | 1971 ⓘ |
| output | YES if the formula is satisfiable, NO otherwise ⓘ |
| practicalRelevance |
used in constraint solving
ⓘ
used in cryptanalysis ⓘ used in hardware verification ⓘ used in planning and scheduling ⓘ used in software verification ⓘ |
| reductionType | polynomial-time many-one reduction ⓘ |
| relatedProblem |
3-SAT
NERFINISHED
ⓘ
Hamiltonian cycle problem NERFINISHED ⓘ QBF (quantified Boolean formula problem) ⓘ circuit-SAT ⓘ clique problem ⓘ graph coloring ⓘ vertex cover ⓘ |
| restriction |
2-SAT is solvable in polynomial time
NERFINISHED
ⓘ
3-SAT is NP-complete ⓘ Horn-SAT is solvable in polynomial time ⓘ k-SAT for k ≥ 3 is NP-complete ⓘ |
| satisfiableIf | there exists at least one assignment making the formula true ⓘ |
| solvedBy | SAT solver ⓘ |
| typicalRepresentation | CNF formula as a conjunction of clauses ⓘ |
| unsatisfiableIf | no assignment makes the formula true ⓘ |
| valueDomain | {true,false} ⓘ |
| variableType | Boolean variable ⓘ |
| worstCaseComplexity | believed not solvable in polynomial time unless P = NP ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: SAT Description of subject: SAT (the Boolean satisfiability problem) is the fundamental decision problem of determining whether there exists an assignment of truth values that makes a given Boolean formula evaluate to true.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.