An Idea For Solving 3SAT

Abstract

Delavar Qasemi*

In this paper, we present an algorithm that can be used to convert φ into a solvable form. This is done using binary combinations and the relations between them. Binary combinations are all 2-Clauses that can be obtained from n literal of φ and with their help we convert φ into a readable form (φ2 ). φ1 and φ2 are equivalent (φ1 is the same as φ2 ), so we can solve φ2 instead of solving φ1 . The algorithm performs the transform operation in 4 steps, and in each step it converts φi to φi+1. φi s and φ are equivalent. It can be proven that in the worst case φ5 is solvable. The time and space order of this algorithm is O(n96).

HTML PDF