Solving MIN ONES 2-SAT as fast as VERTEX COVER

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

reducing symmetries to generate easier sat instances

Finding countermodels is an effective way of disproving false conjectures. In first-order predicate logic, model finding is an undecidable problem. But if a finite model exists, it can be found by exhaustive search. The finite model generation problem in the first-order logic can also be translated to the satisfiability problem in the propositional logic. But a direct translation may not be very efficient. This paper discusses how to take the symmetries into account so as to make the resulting problem easier. A static method for adding constraints is presented, which can be thought of as an approximation of the least number heuristic (LNH). Also described is a dynamic method, which asks a model searcher like SEM to generate a set of partial models, and then gives each partial model to a propositional prover. The two methods are analyzed, and compared with each other.

基于SAT的LTL限界模型检测与验证

模型检测是一种自动验证有限状态系统的形式化方法。状态爆炸问题是模型检测面临的主要挑战，限界模型检测是缓和状态空间爆炸限制的手段之一。该方法通常对限界模型和性质进行编码而转化成SAT问题，依次增加限界值以寻找反例或者无法找到反例而得证。限界模型检测方法往往查错迅速。 基于SAT的限界验证方法是限界模型检测的一个分支。它与限界模型检测的不同在于它不是查找反例，而是验证性质的反命题在限界模型上不可成立。相比于限界模型检测，该方法对于正确性质的验证有时会快许多。但是它不能用来验证含有G算子的LTL公式。鉴于此，我们选取一部分包含G算子的LTL公式。然后在这个公式集合上构造出新的限界验证编码。并且证明了对于该LTL公式子集，我们的编码是可靠并且完备的。新编码可以作为限界验证的一个补充。

一种基于SAT的运算电路查错方法

基于SAT的运算电路查错方法将被验证系统中系统规范成立与否的问题转换为布尔公式和数学公式的混合形式E-CNF，通过采用了标志子句技术的E-SAT求解器进行求解．实验表明该方法自动化程度高，能处理大规模的运算电路，有较强的查找错误能力．

Survey Propagation:一种求解SAT的高效算法

Survey propagation是一种新生的SAT(CSP)算法.它基于统计物理的spin glass模型,针对具体问题进行纵览(survey),从而极大地降低求解的复杂度.但sp算法在某些时候不收敛,或引导向错误的解.对此,G.Parisi提出一种复杂回溯(backtrack)算法,而作者在sp中加入简单回溯,也使一部分此类问题得到解决.

SAT和DSOLS问题的研究

约束可满足性问题（Constraint Satisfaction Problem,CSP）是在人工智能领域被广泛研究的一类问题。对CSP问题的研究有两种重要的思路：一种思路是用统一的模型来表示CSP，然后用针对这个统一模型的通用工具进行求解；另外一种思路是针对不同的CSP问题开发专门工具，设计不同的算法和数据结构来求解。 本文研究了两个CSP问题：SAT(SATisfiability problem)和DSOLS(DoublySelf-Orthogonal Latin Squares)。CSP可以方便的转换为SAT来求解，因此对SAT的研究对很多问题具有重大意义。本文介绍了当前流行的SAT solver的一些技术，也提出一种新的搜索空间裁剪策略Local Lemma。DSOLS是一种具有特定性质的拉丁方，本文对它的研究不仅仅因为它的应用意义。更重要的是它作为一个特定的CSP问题，可以用来比较通用工具和专门工具的优劣。本文尝试了把DSOLS转化为SAT求解，也试过用一般CSP的思路来求解，最后提出了一种针对性的高效算法并开发了一个专门工具DSOLver，用这个工具证明了一个开放问题：DSOLS(10)不存在。

Finding Rough Set Reducts with SAT.

R. Jensen, Q. Shen and A. Tuson, 'Finding Rough Set Reducts with SAT,' Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, LNAI 3641, pp. 194-203, 2005.

tts: A SAT-Solver for Small, Difficult Instances

The Ternary Tree Solver (tts) is a complete solver for propositional satisfiability which was designed to have good performance on the most difficult small instances. It uses a static ternary tree data structure to represent the simplified proposition under all permissible partial assignments and maintains a database of derived propositions known to be unsatisfiable. In the SAT2007 competition version 4.0 won the silver medal for the category handmade, speciality UNSAT solvers and was the top qualifier for the second stage for handmade benchmarks, solving 11 benchmarks which were not solved by any other entrant. We describe the methods used by the solver and analyse the competition Phase 1 results on small benchmarks. We propose a first version of a comprehensive suite of small difficult satisfiability benchmarks (sdsb) and compare the worst-case performance of the competition medallists on these benchmarks.

Zero-One Designs Produce Small Hard SAT Instances

Some basics of combinatorial block design are combined with certain constraint satisfaction problems of interest to the satisfiability community. The paper shows how such combinations lead to satisfiability problems, and shows empirically that these are some of the smallest very hard satisfiability problems ever constructed. Partially balanced (0,1) designs (PB01Ds) are introduced as an extension of balanced incomplete block designs (BIBDs) and (0,1) designs. Also, (0,1) difference sets are introduced as an extension of certain cyclical difference sets. Constructions based on (0,1) difference sets enable generation of PB01Ds over a much wider range of parameters than is possible for BIBDs. Building upon previous work of Spence, it is shown how PB01Ds lead to small, very hard, unsatisfiable formulas. A new three-dimensional form of combinatorial block design is introduced, and leads to small, very hard, satisfiable formulas. The methods are validated on solvers that performed well in the SAT 2009 and earlier competitions.

Parallelization of SAT on Reconfigurable Hardware

Quoique très difficile à résoudre, le problème de satisfiabilité Booléenne (SAT) est fréquemment utilisé lors de la modélisation d’applications industrielles. À cet effet, les deux dernières décennies ont vu une progression fulgurante des outils conçus pour trouver des solutions à ce problème NP-complet. Deux grandes avenues générales ont été explorées afin de produire ces outils, notamment l’approche logicielle et matérielle. Afin de raffiner et améliorer ces solveurs, de nombreuses techniques et heuristiques ont été proposées par la communauté de recherche. Le but final de ces outils a été de résoudre des problèmes de taille industrielle, ce qui a été plus ou moins accompli par les solveurs de nature logicielle. Initialement, le but de l’utilisation du matériel reconfigurable a été de produire des solveurs pouvant trouver des solutions plus rapidement que leurs homologues logiciels. Cependant, le niveau de sophistication de ces derniers a augmenté de telle manière qu’ils restent le meilleur choix pour résoudre SAT. Toutefois, les solveurs modernes logiciels n’arrivent toujours pas a trouver des solutions de manière efficace à certaines instances SAT. Le but principal de ce mémoire est d’explorer la résolution du problème SAT dans le contexte du matériel reconfigurable en vue de caractériser les ingrédients nécessaires d’un solveur SAT efficace qui puise sa puissance de calcul dans le parallélisme conféré par une plateforme FPGA. Le prototype parallèle implémenté dans ce travail est capable de se mesurer, en termes de vitesse d’exécution à d’autres solveurs (matériels et logiciels), et ce sans utiliser aucune heuristique. Nous montrons donc que notre approche matérielle présente une option prometteuse vers la résolution d’instances industrielles larges qui sont difficilement abordées par une approche logicielle.

Cracking the SAT. U.S. and World history subject tests.

Scholastic Aptitude Test (SAT) se trata de una prueba estandarizada usada frecuentemente para valorar los conocimientos adquiridos durante la enseñanza secundaria por los estudiantes que deseen acceder a una educación superior en EE.UU. Esta publicación proporciona la información y las estrategias necesarias para maximizar la puntuación de la prueba del SAT en historia. Enseña a pensar como los redactores de la prueba, y a practicar con la materia que se pondrá en el examen para poder estudiar con mayor eficacia. Se hace una revisión de las épocas históricas que van a aparecer en la prueba y facilita con explicaciones detalladas técnicas para aplicar los conocimientos aprendidos en resolver cuestiones específicas complicadas. Incluye cuatro ensayos prácticos con preguntas de opción múltiple de una hora de duración cada una: dos pruebas de historia de Estados Unidos desde la aprobación de la Constitución hasta la actualidad, y dos pruebas para historia universal.

Cracking the SAT. Biology E, M subject test.

Scholastic Aptitude Test (SAT) se trata de una prueba estandarizada usada frecuentemente para valorar los conocimientos adquiridos durante la enseñanza secundaria por los estudiantes que deseen acceder a una educación superior en EE.UU. Esta publicación proporciona la información y las estrategias necesarias para maximizar la puntuación de la prueba del SAT en biología. Enseña a pensar como los redactores de la prueba, y a practicar con la materia que se pondrá en el examen para poder estudiar con mayor eficacia. Se hace una revisión de los conceptos principales de la biología que van a aparecer en la prueba y facilita, con explicaciones detalladas, estrategias para aplicar los conocimientos aprendidos en resolver cuestiones específicas complicadas. Incluye dos ensayos prácticos de una hora de duración con preguntas de opción múltiple.

Cracking the SAT. Literature subject test.

Scholastic Aptitude Test (SAT) se trata de una prueba estandarizada usada frecuentemente para valorar los conocimientos adquiridos durante la enseñanza secundaria por los estudiantes que deseen acceder a una educación superior en EE.UU. Esta publicación ,proporciona la información y las estrategias necesarias para desarrollar la capacidad de comprender y analizar textos literarios seleccionados de prosa, poesía y teatro escritos en inglés, para maximizar la puntuación de la prueba del SAT en literatura. Enseña a pensar como los redactores de la prueba, y a practicar con la materia que se pondrá en el examen para poder estudiar con mayor eficacia. Se hace una revisión de los conceptos principales de la literatura que van a aparecer en la prueba y facilita con explicaciones detalladas técnicas para aplicar los conocimientos aprendidos en resolver cuestiones específicas complicadas. Incluye cuatro ensayos prácticos de una hora de duración cada uno con preguntas de opción múltiple que se centran en conocimientos básicos de términos literarios.

Cracking the SAT. Math 1 and 2 subject tests.

Scholastic Aptitude Test (SAT) se trata de una prueba estandarizada usada frecuentemente para valorar los conocimientos adquiridos durante la enseñanza secundaria por los estudiantes que deseen acceder a una educación superior en EE.UU. Esta publicación proporciona la información y las estrategias necesarias para maximizar la puntuación de la prueba del SAT en matemáticas. Enseña a pensar como los redactores de la prueba, y a practicar con la materia que se pondrá en el examen para poder estudiar con mayor eficacia. Se hace una revisión de los conceptos principales desde el álgebra básica a la geometría, trigonometría y la estadística que van a aparecer en la prueba y facilita con explicaciones detalladas estrategias para aplicar los conocimientos aprendidos en resolver cuestiones específicas complicadas. Incluye cuatro ensayos prácticos con cincuenta preguntas de selección múltiple de una hora de duración cada uno.