International Journal of Media and Networks(IJMN)
ISSN: 2995-3286 | DOI: 10.33140/IJMN
Impact Factor: 1.02
Review Article - (2025) Volume 3, Issue 5
An Idea For Solving 3SAT
Received Date: Aug 01, 2025 / Accepted Date: Sep 04, 2025 / Published Date: Sep 10, 2025
Copyright: ©2025 Delavar Qasemi. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Citation: Qasemi, D. (2025). An Idea For Solving 3SAT. Int J Med Net, 3(4), 01-07.
Abstract
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).
Introductions and Definitions
literals to it in sequence. For example, the 3-Clause (a+b+c ) can be expanded into 8 6-Clauses.
The 3SAT problem is one of the unsolved problems and no solution has been found yet. Scientists in this field describe these problems as PvsNP. If an algorithm can be found that can solve 3SAT in polynomial time, then P=NP, and if it can be proven that no such algorithm exists, then P!=NP.
PvsNP
Of course, algorithms have been designed that can work in some situations, but these algorithms are random and approximate and cannot provide a definitive answer.
φ has n literals. The literals are the inputs to the problem. Each literal can take the value 0 or 1. In general, literals can have 2n different values. 2n can sometimes be a very large number and its calculation is impossible. For example, for a small n like n = 64 , 264 cannot be calculated and to find it the computer must be turned on for centuries. Computing 264 is not possible even with the fastest systems and will not be possible in the future. This is why we cannot determine whether a problem is SAT or UNSAT by examining all the inputs.
Clauses express constraints and dos and don'ts on literals. For example, (x + y + z) requires literals x, y, z not to be 0 at the same time. The more clauses in a problem, the more information can be obtained about the paths and relationships between literals. . New clauses can be discovered by methods such as merging, but the question is, what is the minimum number of clauses and of what length do we need to solve the problem? There is no answer for the value of k , and in the worst case, k is considered equal to n .
2-Clauses and Binary Combinations
2-Clauses are the conjunction of two literals or their opposites. For example, (a+b) is a 2-Clause that states that a and b must not be 0 at the same time.2-clauses have an important property that other k-clauses do not have. It can be proven with certainty
property only holds true for 2-Clauses. Merging 3-Clauses may result in a 2-, 3-, or 4-Clause.
We use this property of 2-Clauses. To begin with, it is enough to know that any 3-Clause like (a + b + c) is the product of + two 2-Clauses like (a+ b) and (b + c) . Or a 4-Clause like (a + b + c + d) is the product of + two 2-Clauses like (a + b) and (c + d).
Binary combinations are the basis of our algorithm. Binary combinations are the set of all 2-Clauses that can be obtained from n literals of φ . The number of binary combinations is 4n2 . We labele each binary combination with a new variable like
Rewriting Clauses with New Variables
We can rewrite the clauses of φ with new variables and arrive at equivalent clauses.
Lemma 1 :
Assuming the following variables
A1 = (x + y), A2 = (x +z), A3 = (y+ z), A4 =(x+ x), A5 =(y+ y), A6 = (z+ z)
,we can express (x + y + z) as follows.
( A1 + A2 )( A1 +A3 )( A2 + A3 )( A1 + A6 )( A2 + A5 )( A3 + A4 )
Proof :
According to truth table 1, (x + y + z) and ( A1 + A2 )( A1 + A3 )( A2 + A3 )( A1 + A6 )( A2 + A5 )( A3 + A4 ) are equivalent to each other.
Truth Table 1
Relationships Between Binary Combination
We have already mentioned that a new 2-Clause can be derived from merge of other 2-Clauses. To show these relationships, we use the change of variable and new clauses.Lemma 2 :
proof : Truth Table 2Shows the Truth of the Relations.
Truth Table 2
Flow Chart
Theorems
Theorem 1 :φ and φi s are equivalent to each other.
Proof: To prove equivalence, it is enough to substitute the values of the variables in φi s to obtain φ again.
M2 2 * N2 * N2 * N2 = M 22 N2 3
Conclusion
We conclude that the idea of changing the variable is a new approach to solving the 3SAT problem. Using binary combinations as new variables can be useful because we can express the relationships between them and use their relationships to solve φ . As we have shown, in step 4, it is determined whether φ5 is SAT or UNSAT. The largest space required is 6- Clauses of φ5 . Therefore, the 3SAT problem can be solved in space and time complexity O(N56 ) = O((n16 )6 ) O(n96 ) .
References
- Krom, M. R. (1967). hedecisionproblemforaclassoffirst-orderformulasinwhichalldisjunctionsarebinary.WILEY,13(1–2),15–20