|
|
|
|
|
Francisco Miguel García-Olmedo, Jesús García-Miranda and Pedro González-Rodelas
The conjunctive normal form (CNF) algorithm is one of the best known and most widely used algorithms in classical logic and its applications. In its algebraic approach, it makes use in a loop of a certain well-defined operation related to the ?distributi...
ver más
|
|
|
|
|
|
|
|
|
|
|
Tomohiro Sonobe
It has been proven that extended resolution (ER) has more powerful reasoning than general resolution for the pigeonhole principle in Cook?s paper. This fact indicates the possibility that a solver based on extended resolution can exceed Boolean satisfiab...
ver más
|
|
|
|
|
|
|
|
|
|
|
Aleksey I. Pakhomchik, Vladimir V. Voloshinov, Valerii M. Vinokur and Gordey B. Lesovik
There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using t...
ver más
|
|
|
|
|
|
|
|
|
|
|
Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble and George Siopsis
We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary ...
ver más
|
|
|
|
|
|
|
|
|
|
|
Johannes K. Fichte, Markus Hecher, Michael Morak and Stefan Woltran
Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been establish...
ver más
|
|
|
|
|
|
|
|
|
|
|
Abdelraouf Ishtaiwi and Qasem Abu Al-Haija
The Maximum Satisfiability (Maximum Satisfiability (MaxSAT)) approach is the choice, and perhaps the only one, to deal with most real-world problems as most of them are unsatisfiable. Thus, the search for a complete and consistent solution to a real-worl...
ver más
|
|
|
|
|
|
|
|
|
|
|
Gábor Kusper and Csaba Biró
In a previous paper we defined the black and white SAT problem which has exactly two solutions, where each variable is either true or false. We showed that black and white 2-SAT problems represent strongly connected directed graphs. We presented also the...
ver más
|
|
|
|
|
|
|
|
|
|
|
Ivan Chizhov,Nataliia Tashevtseva
Pág. 27 - 38
The authors propose an algorithm, which converts input for the cryptoanalyst problem of revealing secret keys of CodeBased Signature Scheme pqsigRM to an equal input for the SATISFIABILITY problem. It is proved in the paper, that the proposed attack is p...
ver más
|
|
|
|
|
|
|
|
|
|
|
Oleg Zaikin,Stepan Kochemazov
Pág. 5 - 10
Many state-of-the-art algorithms for solving Boolean satisfiability problem (SAT) are based on the CDCL algorithm. CDCL generates a lot of so-called conflict clauses that correspond to traversed branches of a tree of possible solutions. To maintain high ...
ver más
|
|
|
|
|
|
|
|
|
|
|
Wenxing Lai
Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para-??????
AC
0
and the k-DominatingSet (k-DomSet) problem could not be computed by para-??????
AC
0
circuits. It is natural to ask whether the ??(??)
f
(
k
)
-approxima...
ver más
|
|
|
|
|
|