Loss function seems to be used to solve optimization problems. I assumed that 3SAT problems can be treated as them. I would like to know whether there is a good loss function that is defined by clauses of the 3-CNF. I tried to define the function like this.
$A \lor B$ -> $(1-P_A)(1-P_B)$
$A \lor B \lor C$ -> $(1-P_A)(1-P_B)(1-P_C)$
Loss function = $\Sigma (1-P_i)(1-P_j)(1-P_k)$
$P$ means continuous truth value that can be interpreted as probability($0 \leq P \leq 1$). It is considered that each literal in the clause can not be false simultaneously. If the value of the loss function can reach zero, then it means that we found solutions.
However, it doesnt't work well. The reason seems that the $-\nabla(1-P_A)(1-P_B)$ leads the truth values to (1, 1) and ignores the possible combinations (0, 1), (1, 0). I tried to modify the definition to capture the property of the problems(example: power of the function). Consequently, I didn't find the appropriate definition.
I would like to know whether there is a theory or a thesis about this approach, and what is the best defintion of the loss function for 3SAT problems. The algorithms that don't have 100% accuracy are fine.
You can instead introduce nonnegative slack variables $S_{ijk}$ and $T_{ijk}$ and minimize $$\sum_{i,j} S_{ij} + \sum_{i,j,k} T_{ijk}$$ subject to linear constraints \begin{align} P_i + P_j + S_{ij} &\ge 1 \\ P_i + P_j + P_k + T_{ijk} &\ge 1 \end{align} The objective value is $0$ if and only if all clauses are satisfied.