File:CNF-SAT-independent-set-reduction.svg

Summary

Description Demonstrates the key gadget for polytime reduction from the NP-complete CNF-SAT (conjunction normal form satisfiability) problem to the independent set problem, a graph problem. Created by Derrick Coetzee in Adobe Illustrator. Intended to replace en:Image:CNF-SAT-independent-set-reduction.png, which was derived from the same source file.
Date 31 December 2005 (original upload date)
Source No machine-readable source provided. Own work assumed (based on copyright claims).Category:Assumed own work
Author No machine-readable author provided. Dcoetzee assumed (based on copyright claims). Category:Files with no machine-readable source

Licensing

Public domain I, the copyright holder of this work, release this work into the public domain. This applies worldwide.
In some countries this may not be legally possible; if so:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.
Category:Self-published work#CNF-SAT-independent-set-reduction.svgCategory:PD-self#CNF-SAT-independent-set-reduction.svg Category:Boolean satisfiability problem Category:2x3 arrays Category:Graphs with 6 vertices Category:Independent set (graph theory)
Category:2x3 arrays Category:Assumed own work Category:Boolean satisfiability problem Category:Files with no machine-readable source Category:Graphs with 6 vertices Category:Independent set (graph theory) Category:PD-self Category:Self-published work