The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Apr. 08, 2008
Filed:
Feb. 27, 2004
Evgueni Goldberg, Berkeley, CA (US);
Yakov Novikov, Minsk, BY;
Evgueni Goldberg, Berkeley, CA (US);
Yakov Novikov, Minsk, BY;
Cadence Design Systems, Inc., San Jose, CA (US);
Abstract
A method and system for solving satisfiability problems is disclosed. In one embodiment, clauses in a satisfiability problem are organized as a chronologically ordered stack. In another embodiment, the activity of each variable in the satisfiability problem is monitored. An activity counter is maintained for each variable and is incremented each time the variable appears in a clause used in generating a conflict clause. In an embodiment, a branching variable is selected from among the variables in the top clause of the stack when the top clause is a conflict clause. In a further embodiment, one or more conflict clauses in the stack are removed when the search tree is abandoned. In a still further embodiment, the value assigned to a branching variable is selected for purposes of having a uniform distribution of positive and negative literals.