2 exercises
Tagged:
  • sat x

Start over - to expand, or dig in by adding more tags and revising the query.

Sort By: trending ▼ date
0
Undergraduate
By John Doe on Nov. 3, 2012 | Updated Dec. 6, 2017

Direct reduction from Graph Homomorphism to SAT

The decision problem \(GraphHomo\) is defined as follows: \(GraphHomo = \{\langle G, H\rangle \mid \text{there is a graph homomorphism from G to H}\}\) Give a direct reduction from \(GraphHomo\) to …
0
Undergraduate
By Shiva Kintali on Nov. 14, 2012 | Updated Dec. 6, 2017

Randomized k-SAT algorithm

Consider an instance of SAT with \(m\) clauses, where every clause has exactly \(k\) literals. Give a Las Vegas algorithm that finds an assignment satisfying at least \(m(1-2^{-k})\) clauses, and an…
Post Something
x

Select What You'd Like To Post

POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION

Content Types

Social learning platform. © 2016 True Group Inc. All Right Reserved