2010Jisuanji yingyong yanjiuRequires access

New SAT solver based on finding satisfiable 2-SAT sub problem

Zhou Yu-ren

Open publisher page 0 citations

Abstract

Satisfiability(SAT) problem is one of the NP-Hard problems.This paper introduced a new SAT solver called FSSAT.This SAT solver solved the problem by searching a satisfiable 2-SAT sub problem.SAT was NP-complete,but it can be solved in linear time when the given formula contains only binary clauses(2-SAT).BinSat(2-SAT solver) was used to solve the 2-SAT sub problem and improved the 2-SAT sub problem according to the truth assignment.The experimental results show that the solver outperforms UnitWalk.

About this research paper

What this paper is about

Satisfiability(SAT) problem is one of the NP-Hard problems.This paper introduced a new SAT solver called FSSAT.This SAT solver solved the problem by searching a satisfiable 2-SAT sub problem.SAT was NP-complete,but it can be solved in linear time when the given formula contains only binary clauses(2-SAT).BinSat(2-SAT solver) was used to solve the 2-SAT sub problem and improved the 2-SAT sub problem according to the truth assignment.The experimental results show that the solver outperforms UnitWalk.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Satisfiability(SAT) problem is one of the NP-Hard problems.This paper introduced a new SAT solver called FSSAT.This SAT solver solved the problem by searching a satisfiable 2-SAT sub problem.SAT was NP-complete,but it can be solved in linear time when the given formula contains only binary clauses(2-SAT).BinSat(2-SAT solver) was used to solve the 2-SAT sub problem and improved the 2-SAT sub problem according to the truth assignment.The experimental results show that the solver outperforms UnitWalk.

Key concepts: Boolean satisfiability problem, Solver, Computer science, Satisfiability, Maximum satisfiability problem, Problem solver, Algorithm, Boolean function

Related papers

Back to paper searchBrowse research topicsOriginal source
New SAT solver based on finding satisfiable 2-SAT sub problem — Research Paper | ScholarLens