Image: Schaefer's 3-SAT to 1-in-3-SAT reduction
Size of this preview: 800 × 193 pixels. Other resolutions: 320 × 77 pixels | 1,159 × 279 pixels.
Original image (1,159 × 279 pixels, file size: 19 KB, MIME type: image/gif)
Description: 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.
Title: Schaefer's 3-SAT to 1-in-3-SAT reduction
Credit: Own work
Author: Jochen Burghardt
Usage Terms: Creative Commons Attribution-Share Alike 3.0
License: CC BY-SA 3.0
License Link: https://creativecommons.org/licenses/by-sa/3.0
Attribution Required?: Yes
Image usage
The following page links to this image:
All content from Kiddle encyclopedia articles (including the article images and facts) can be freely used under Attribution-ShareAlike license, unless stated otherwise.
