Statements (21)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
Boolean satisfiability problem |
| gptkbp:alsoKnownAs |
gptkb:NAE-3SAT
|
| gptkbp:clauseType |
Not-All-Equal
|
| gptkbp:definedIn |
theory of computational complexity
|
| gptkbp:firstProvedNPCompleteBy |
gptkb:Schaefer
|
| gptkbp:firstProvedNPCompleteIn |
1978
|
| gptkbp:generalizes |
gptkb:Not-All-Equal_k-SAT
|
| gptkbp:hasSpecialCase |
gptkb:Not-All-Equal_SAT
|
| https://www.w3.org/2000/01/rdf-schema#label |
Not-All-Equal 3SAT
|
| gptkbp:input |
Boolean formula in conjunctive normal form with 3 literals per clause
|
| gptkbp:NP-complete |
true
|
| gptkbp:numberOfLiteralsPerClause |
3
|
| gptkbp:output |
YES if there is a Not-All-Equal assignment, NO otherwise
|
| gptkbp:relatedTo |
gptkb:3SAT
|
| gptkbp:satisfyingAssignmentCondition |
each clause has at least one true and one false literal
|
| gptkbp:usedIn |
complexity reductions
proofs of PCP theorem theory of hardness of approximation |
| gptkbp:bfsParent |
gptkb:NP_languages
|
| gptkbp:bfsLayer |
6
|