The ability of invertible logic circuits to operate in reverse gives rise to a convenient method of solving inverse problems, as noted in the related paradigm of memcomputing and by D-Wave [1]}, [2]}. Therefore, hard combinatorial optimization problems such as integer factorization and Boolean satisfiability (SAT) can be solved in hardware using invertible multipliers or by invertible Boolean circuits corresponding to a given satisfiability instance. Fig. REF a shows a classic \(m\) -bit multiplier circuit composed of multiple AND gates and FAs. In the reverse direction, this circuit works as an \(n\) -bit factorizer circuit (\(n = 2m\) ) where we clamp the output bits to the \(n\) -bit product to be factored. Similarly, we clamp the output of the SAT solver circuit in Fig. REF b to 1 and find the input variables satisfying all the clauses in the reverse direction. Each clause is represented by multiple OR gates; if any input variable is negated, we modify the corresponding weight (\(J\) ) matrix of the OR gate accordingly. The output bits of the OR gates can be clamped to 1 either directly or by using an AND gate at the end. In this work, we primarily focus on the 3SAT, a special form of the satisfiability problem where each clause has exactly three variables in the conjunctive normal form (CNF) [3]}. We collected 3SAT instances as `.CNF' files from the UBC SATLIB library [4]} and map them to interconnection matrices (\(J\) ), composed of elementary probabilistic gates.
