3-SAT worms clicks

The 3-SAT worms clicks is a mathematical question of logic.

Polynomial reduction

To reduce the problem 3-SAT towards that of the clicks, with each formula 3-CNF, one associates a graph not directed of which the number of tops is three times in the following way the number of clauses:

with each of the three literal ones of each clause, one associates a top;
one connects the tops by edges in the following way: two tops which are associated with literal with the same clause are not connected by an edge, two tops which are associated with literal and its negation are not connected either, all the other couples of tops are connected.

It is shown whereas the formula with $k$ clauses is satisfiable if and only if the graph has one clicks order $k$ .

Idea of the proof:

If the formula is satisfiable, there exists an assignment of the variables for which the value of at least literal of each clause is TRUE. The formed whole of the tops associated with the one with these literal by clause is one clicks graph.

If the graph has one clicks order $k$ , it contains exactly a top among the three which represents literal each clause; one can define an assignment of the variables for which the value of these literal is TRUE; the value of the formula for this assignment is then TRUE.

Random links: