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

From Wikimedia Commons, the free media repository

Jump to: navigation, search

CNF-SAT-independent-set-reduction.svg‎ (SVG file, nominally 122 × 101 pixels, file size: 16 KB)

[edit] Summary

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.

[edit] Licensing

Public domain I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide.

In case this is not legally possible:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Afrikaans | Alemannisch | Aragonés | العربية | Asturianu | Azərbaycan | Беларуская (тарашкевіца) | Български | Català | Cebuano | Soranî / کوردی | Česky | Cymraeg | Dansk | Deutsch | Ελληνικά | English | Esperanto | Español | Eesti | Euskara | Estremeñu | فارسی | Suomi | Français | Galego | עברית | हिन्दी | Hrvatski | Magyar | Հայերեն | Bahasa Indonesia | Ido | Íslenska | Italiano | 日本語 | ქართული | ភាសាខ្មែរ | 한국어 | Ripoarisch | Kurdî / كوردی | Latina | Lietuvių | Latviešu | 文言 | Македонски | Bahasa Melayu | Plattdüütsch | Nederlands | ‪Norsk (nynorsk)‬ | ‪Norsk (bokmål)‬ | Polski | Português | Română | Русский | Slovenčina | Slovenščina | Shqip | Српски / Srpski | Svenska | ไทย | Tagalog | Türkçe | Українська | Vèneto | Tiếng Việt | Walon | 吴语 | 中文 | ‪中文(简体)‬ | ‪中文(繁體)‬ | 粵語 | +/−

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current22:42, 31 December 2005Thumbnail for version as of 22:42, 31 December 2005122×101 (16 KB)Dcoetzee (talk | contribs) (Fix ugly x's (font issue))
22:40, 31 December 2005Thumbnail for version as of 22:40, 31 December 2005122×101 (9 KB)Dcoetzee (talk | contribs) (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 t)

The following 2 pages link to this file:

Global file usage

The following other wikis use this file:

Retrieved from "http://commons.wikimedia.org/wiki/File:CNF-SAT-independent-set-reduction.svg"