<figure><img src="image_1.png" /></figure>

HAL
open science

# A Combinatorial Approach to SAT

Abdulrhman Elnekiti

► To cite this version:

Abdulrhman Elnekiti. A Combinatorial Approach to SAT. 2018. hal-01944061v2

HAL Id: hal-01944061

https://hal.science/hal-01944061v2

Preprint submitted on 16 Dec 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# A Combinatorial Approach to SAT

Abdulrhman Elnekiti

Department of Computer Science - THK University

Abdulrhman.Elnekiti@stu.thk.edu.tr

http://ceng.thk.edu.tr/en

**Abstract.** An approach to the satisfiability problem SAT is proposed in (4) steps. A satisfying assignment is formed (if exists) using the literals.

## 1 Preliminaries

The Satisfiability Problem SAT is a constraint satisfaction problem formulated on *N* Boolean variables $x_i \in \{0,1\}$, $i = 1$ to *N* and *M* clauses $C_1$ to $C_M$. A clause *cla* is a set of literals, a literal *lit* is the positive form $x_i = 1$ or the negated form $\bar{x_i} = 0$ of a variable $x_i$. A conflict of $x_i$, written *conflict* ($x_i$), exists when both 0 and 1 are set to $x_i$, $x_i = \{0,1\}$. A SAT instance is in conjunctive normal form CNF if it is the conjunction of clauses and the disjunction of literals [2] [3].

## 2 The Approach

Let $\alpha$ be a SAT instance in CNF and A be a set :

1. $\forall cla \in \alpha$ (add a lit $\in cla$ to A)

2. $\forall x_i \notin A$ (set $x_i$ to 0 or 1 in A)

3. If $(\forall x_i(conflict(x_i) \notin A)), A$ satisfies $\alpha$

4. If $(\forall A(conflict(x_i) \in A)), \alpha$ is UNSAT

*Step* (1) shows the formation of an assignment *A* to *α* by choosing a literal from each clause in *α* and inserting it to *A*. *Step* (2) is used to arbitrarily set the missing $x_i$ (if any) in *A* to 0 or 1 then add it to *A*. If *conflict* ($x_i$) for all $x_i$ does not exist in *A*, then *A* is a satisfying assignment to *α*. If *conflict* ($x_i$) for any $x_i$ exists in all *A* that can be obtained from *α*, then *α* is *unsatisfiable* (UNSAT).

## 3 References

1. Abdurhman Elnekiti, *New Directions in Cellular Automata*, https://arxiv.org/abs/1705.05832

2. Stephen Cook, *The P vs NP Problem*, https://www.claymath.org/sites/default/files/pvsnp.pdf

3. Stephen Cook, *Complexity of Theorem Proving Procedures*, https://www.cs.toronto.edu/~sacook/homepage/1971.pdf