File:Schaefer's 3-SAT to 1-in-3-SAT reduction.gif
From Infogalactic: the planetary knowledge core
Size of this preview: 800 × 193 pixels. Other resolutions: 320 × 77 pixels | 1,159 × 279 pixels.
Original file (1,159 × 279 pixels, file size: 19 KB, MIME type: image/gif)
Summary
The left table shows the 1-in-3-SAT clauses Schaefer's reduction maps a 3-SAT clause x∨y∨z to. a,...,f are fresh variables; the result of R is true iff exactly one of its arguments is. All 8 combinations of values for x,y,z are examined, one per line. The reduction is satisfiable iff x∨y∨z is true. The right table shows a simpler reduction with the same properties.
Licensing
Lua error in package.lua at line 80: module 'strict' not found.
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 09:10, 13 January 2017 | | 1,159 × 279 (19 KB) | 127.0.0.1 (talk) | The left table shows the 1-in-3-SAT clauses Schaefer's reduction maps a 3-SAT clause <i>x</i>∨<i>y</i>∨<i>z</i> to. <i>a</i>,...,<i>f</i> are fresh variables; the result of <i>R</i> is true iff exactly one of its arguments is. All 8 combinations of values for <i>x</i>,<i>y</i>,<i>z</i> are examined, one per line. The reduction is satisfiable iff <i>x</i>∨<i>y</i>∨<i>z</i> is true. The right table shows a simpler reduction with the same properties. |
- You cannot overwrite this file.
File usage
The following page links to this file:
