Patent ID: 11923009
Assignee: HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP
Field: Computer technology (Electrical engineering)
Classification: CPC G  H | IPC G  H

Claim 16:
17. A circuit for solving a K-SAT problem comprising:
a K-SAT verification circuit configured to:
program one or more clauses of a Boolean expression for a K-SAT problem written in negated disjunctive normal form (DNF) to a TCAM array comprising columns and rows of TCAM cells, wherein each clause of the Boolean expression is programmed to a respective cell of a row of the TCAM array, and wherein each occurring variable of each clause is mapped to a respective cell of the row, and wherein each non-occurring variable is programmed as a don't care value;
apply an interpretation comprising search data to one or more search lines of the TCAM array, wherein the search data includes one or more binary variables expected to solve the Boolean expression, and wherein the search data is applied as an input along the one or more search lines; and
discharge a match line if a row does not include the search data; and

a K-SAT optimizer, configured to:
update the interpretation if at least one match line is not discharged.