1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes your method does find a correct loss function that has same objective but this function is not convex, there for gradient decent won’t typically work. $\endgroup$
    – P. Quinton
    Commented Apr 7, 2022 at 13:03

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Then, can this type of problems be solved by simplex method? Is it efficient? $\endgroup$
    – cozzie9806
    Commented Apr 8, 2022 at 7:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .