3 items
Topic:

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
Graduate
By Shiva Kintali on June 10, 2012 | Updated Dec. 6, 2017

Parity is non-monotone

A boolean function \(f(x_{1},x_{2},\dots,x_{n})\) is called monotone if it can be written as a formula with only the AND and OR operations. Prove that \(x_1 \oplus x_2 \oplus \dots \oplus x_n\) is n…
0
Graduate
By diego on June 22, 2012 | Updated Dec. 6, 2017

The power of the majority function

A boolean function \(f(x_{1},x_{2},\dots,x_{n})\) is called monotone if it can be written as a formula with only the AND and OR operations and constants 0 and 1; and it is called self-dual if …
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