File:3SAT reduced too VC(1).svg
![File:3SAT reduced too VC(1).svg](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/3SAT_reduced_too_VC%281%29.svg/384px-3SAT_reduced_too_VC%281%29.svg.png?20150821203850)
Original file (SVG file, nominally 384 × 257 pixels, file size: 11 KB)
Captions
Captions
Summary
[edit]Description3SAT reduced too VC(1).svg |
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 |
Licensing
[edit]Public domainPublic domainfalsefalse |
![]() |
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.Public domainPublic domainfalsefalse |
Original upload log
[edit]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/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 20:38, 21 August 2015 | ![]() | 384 × 257 (11 KB) | Mike Hayes (talk | contribs) | Transferred from en.wikipedia |
You cannot overwrite this file.
File usage on Commons
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.
Width | 384 |
---|---|
Height | 257 |