Question

Call a log-space reduction a reduction that uses only O(logn) space in addition to the input itself, and not counting the produced result. In other words, there are three tapes: tape 1 is read-only (the input), tape 2 is read-write (the work tape), and tape 3 is write-only (the output tape). Then we insist that tape 2 use O(logn) space (tape 3 is unrestricted, but remember it is write-only). Such a reduction is denoted ≤L. Show that 3SAT ≤L CLIQUE.

Answer 1

Answer: Every boolean formula can be written as  

(...v..v....) ^ (v...v...v) ^ ... this is called conjuctive nomal form (CNF) where v is nothing but varables

each set of variables denotes clauses so clause 1 & clause 2 respectively from above

so the both clauses to be satisfied i.e they should be evaluated since it is connected by and (^)

failing which the whole formula will not be satisfied.

So, if one of the clauses is not satisfied, the whole formula won't be satisfied.

Let G be an undirected graph. A clique in G is a set A of vertices such that all possible edges between elements of A exist in G.

Any vertex forms a clique of size 1, the endpoints of any edge form a clique of size 2, and any triangle is a clique of size 3. The CLIQUE language is a set of pairs (G, k) such that G is an undirected graph that contains some clique of k size.

It should be that CLIQUE is in the class NP. NP-procedure has an arbitrary set A of vertices (with known bitvector of n length). Then the verification phase checks that A has size exactly k and that there is an edge between every pair of vertices in A.

We’ll prove CLIQUE to be NP-complete by reducing 3- SAT to it. Recall means defining a function from 3-CNF formulas to graph-integer pairs, such that satisfiable formulas are mapped to pairs (G, k) such that G has a k-clique and thus unsatisfiable formulas are mapped to pairs where G does not have a k-clique. The main element of any reduction is a correspondence between the two NP-problems. The possible cliques are also denoted by bitvectors, Even the 3-CNF formula is satisfied or not satisfied by a bitvector of length n.

We' ve to make the graph so that a satisfying instance corresponds to a k-clique and vice versa, and we get to pick k for our instances. Here’s the construction.

We have a node for each of a literal in the formula. So if there are m clauses, each with ki literals, the number of vertices the graph is the sum from 1 to m of ki .

Now we need edges. We place an edge between nodes x and y if they refer to literals that occur in different clauses and are not in conflict. We set k to be m, the number of clauses.

Nodes: Appearances of literals in clauses

Edges: Pairs of nodes that are in different clauses and not in conflict.

We prove that the 3-CNF formula is satisfiable if there is an m-clique in the graph. First assume that there is a satisfying assignment, which means that there is at least one literal in each clause that is set true. Fix a set containing exactly one true literal in each clause.

The m nodes corresponding to these literals must form a clique. No two of them are in the same clause, and no two of them can be in conflict, so all possible edges between then exist.

Conversely, suppose that we have an m-clique in the graph. The m nodes must occur in m different clauses, since edges only connect nodes in different clauses. Because the m nodes also contain no conflicts, we can construct a setting of the variables consistent with all those literals. This setting makes at least one literal in each clause true, so it satisfies the formula.

Note: We may have to arbitrarily set variables that don’t occur in the set either as true or as false

REDUCTION OF 3SAT ≤L CLIQUE:

FOR A given graph G= (V,E) and integer k, find if G contains a clique of size >=k

A formula 3-literal clauses can be reduced to a k-clique problem & follow the following steps below

• Construct a graph G of k clusters with max of 3 nodes in each cluster.
• Each cluster corresponds to clause in
• Each node in cluster is labelled with a literal from clause
• An edge is put between pairs of nodes in different clusters except for pairs of (x,) form
• No edge is put between any pair of nodes in same cluster.

1. construction of cluster of nodes corr to clauses in 3 CNF