Close
Register
Close Window

Data Structures and Algorithms

Chapter 11 Limits to Computing (optional)

Show Source |    | About   «  11.14. Reduction of SAT to 3-SAT (optional) (WORK IN PROGRESS)   ::   Contents   ::   11.16. Reduction of Clique to Independent Set (optional) (WORK IN PROGRESS)  »

11.15. Reduction of 3-SAT to Clique (optional) (WORK IN PROGRESS)

11.15.1. Reduction of 3-SAT to Clique

The following slideshow shows that an instance of 3-CNF Satisfiability problem can be reduced to an instance of Clique problem in polynomial time.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Clique problem.

   «  11.14. Reduction of SAT to 3-SAT (optional) (WORK IN PROGRESS)   ::   Contents   ::   11.16. Reduction of Clique to Independent Set (optional) (WORK IN PROGRESS)  »

nsf

© Copyright 2016 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Nov 16, 2022. Created using Sphinx 2.4.4.
Close Window