Hard instance generation for SAT

Details Hard instance generation for SAT Hard instance generation for SAT

1998-09-28

arxiv.org/abs/cs/9809117v2

In the Proc. of ISAAC'97, Lecture Notes in CS, Vol.1350, 22-31, 1997

Computer Science

Computational Complexity

Scientific paper

We propose an algorithm of generating hard instances for the Satisfying Assignment Search Problem (in short, SAT). The algorithm transforms instances of the integer factorization problem into SAT instances efficiently by using the Chinese Remainder Theorem. For example, it is possible to construct SAT instances with about 5,600 variables that is as hard as factorizing 100 bit integers.

Affiliated with

Also associated with

No associations

Rating

Hard instance generation for SAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hard instance generation for SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hard instance generation for SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-481998