SHMARQL

3-satisfiability problem

<http://www.wikidata.org/entity/Q339688>

special case of the Boolean satisfiablility problem in conjunctive normal form where each clause has ≤3 literals
3-satisfiability problem
rdfs:label
"3-satisfiability problem"@en
skos:altLabel
"3-SAT"@en
"3-satisfiability"@en
"3CNFSAT"@en
"3SAT"@en
schema:description
"special case of the Boolean satisfiablility problem in conjunctive normal form where each clause has ≤3 literals"@en
schema:dateModified "2025-06-16T20:28:50+00:00"^^xsd:dateTime
schema:version 2362207281
wikibase:identifiers 2
wikibase:sitelinks 6
wikibase:statements 9
p:P10374 wd:statement/Q339688-1B5CA275-26C7-4E88-91CD-D84A74C03C40
p:P1482 wd:statement/Q339688-7567df91-4a71-3e63-2b70-3bb5e152aedc
wd:statement/Q339688-f45449db-431e-d16c-fb11-c1d4c9a0cdd1
p:P18 wd:statement/Q339688-bd217642-4d53-fe0d-b1f6-b0d39a6c186a
p:P2671 wd:statement/Q339688-00FD1597-3E0D-426A-A7AD-45153F3716E7
p:P31 wd:statement/Q339688-5C697390-1761-4C7A-8BC7-A5992D91B535
wd:statement/Q339688-9ff60df8-4f75-cd12-14c9-3fdc07a476d2
p:P361 wd:statement/Q339688-32a8ee93-431e-cd3d-d97c-69807d3de742
p:P6564 wd:statement/Q339688-cc0bacd7-4d83-a5ba-9403-f20a793e4d32
p:direct-normalized/P2671 <http://g.co/kg/g/1229kf2b>
wdt:P10374 NP-complete
wdt:P1482 <https://cs.stackexchange.com/tags/3-sat>
<https://quantumcomputing.stackexchange.com/tags/3sat-problem>
wdt:P18 <http://commons.wikimedia.org/wiki/Special:FilePath/Sat%20reduced%20to%20Clique%20from%20Sipser.svg>
wdt:P2671 "/g/1229kf2b"
wdt:P31 NP-complete
computational problem
wdt:P361 Karp's 21 NP-complete problems
wdt:P6564 "3sat"
Download as:
TurtleJSON-LDRDF/XML
data from SPARQL profile: Wikidata