File:3SAT reduced too VC(1).svg

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

Original file ‎(SVG file, nominally 384 × 257 pixels, file size: 11 KB)

Captions

Captions

Add a one-line explanation of what this file represents

Summary[edit]

Description
English: Example of the 3-SAT problem reduced in PTIME and PSPACE to the vertex cover problem.

Blue vertices form a partial vertex cover, in the sense that the image is not showing the correct solution to Vertex Cover problem. In the correct solution, the B in the left most triangle should be blue as well, and there should be a line from the other A to the A above. Source of solution from: http://www.cs.bc.edu/~alvarez/Theory/npcompleteness.html

3-sat = {A, B', C}
Date
Source Own work based on: 3SAT reduced too VC.png
Author
SVG development
InfoField
 
The SVG code is valid.
 
This diagram was created with Inkscape.

Licensing[edit]

Public domain This work has been released into the public domain by its author, Booyabazooka at English Wikipedia. This applies worldwide.
In some countries this may not be legally possible; if so:
Booyabazooka grants anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Original upload log[edit]

The original description page was here. All following user names refer to en.wikipedia.
Date/Time Dimensions User Comment
2008-10-05 03:29 384×257× (11520 bytes) Booyabazooka {{Information |Description=Example of the 3-SAT problem reduced in PTIME and PSPACE to the vertex cover problem. Blue vertices form a vertex cover. 3-sat = {A, B', C} |Source=[[:Image:3SAT reduced too VC.png]] |Date=October 4, 2008 |Author=~~~ |other_ve

File history

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

Date/TimeThumbnailDimensionsUserComment
current20:38, 21 August 2015Thumbnail for version as of 20:38, 21 August 2015384 × 257 (11 KB)Mike Hayes (talk | contribs)Transferred from en.wikipedia

You cannot overwrite this file.

There are no pages that use this file.

Metadata

This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.

Retrieved from "https://commons.wikimedia.org/w/index.php?title=File:3SAT_reduced_too_VC(1).svg&oldid=767873211"