Results 21 to 30 of about 770 (181)
The Complexity of Generalized Satisfiability for Linear Temporal Logic [PDF]
Logical Methods in Computer Science, 2009 In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used.
Michael Bauland +4 more
doaj +1 more source
Satisfiability of Quantified Boolean Announcements
CoRR, 2022 The authors regret that the proof of decidability of satisfiability of BAPAL in the previous versions contains errors and they have not been able to correct these errors. We still believe that it is likely that BAPAL is decidable, and we would like to encourage readers to show this independently.
van Ditmarsch, Hans +2 more
openaire +2 more sources
Expected number of locally maximal solutions for random Boolean CSPs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 For a large number of random Boolean constraint satisfaction problems, such as random $k$-SAT, we study how the number of locally maximal solutions evolves when constraints are added.
Nadia Creignou +2 more
doaj +1 more source
Higher-order quantified Boolean satisfiability [PDF]
, 2022 The Boolean satisfiability problem plays a central role in computational complexity and is often used as a starting point for showing NP lower bounds. Generalisations such as Succinct SAT, where a Boolean formula is succinctly represented as a Boolean circuit, have been studied in the literature in order to lift the Boolean satisfiability problem to ...
Chistikov, Dmitry +3 more
openaire +3 more sources
Model-Checking Problems as a Basis for Parameterized Intractability [PDF]
Logical Methods in Computer Science, 2005 Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form.
Joerg Flum, Martin Grohe
doaj +1 more source
Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
Scientific Reports, 2018 Boolean satisfiability (k-SAT) is an NP-complete (k ≥ 3) problem that constitute one of the hardest classes of constraint satisfaction problems. In this work, we provide a proof of concept hardware based analog k-SAT solver, that is built using Magnetic ...
Parami Wijesinghe +2 more
doaj +1 more source
IEEE Transactions on Quantum Engineering, 2021 Experimental demonstrations of quantum annealing with “native” implementation of Boolean logic Hamiltonians are reported. As a superconducting integrated circuit, a problem Hamiltonian whose set of ground states is consistent with a given ...
Daisuke Saida +6 more
doaj +1 more source
Practical applications of Boolean Satisfiability [PDF]
2008 9th International Workshop on Discrete Event Systems, 2008 Boolean satisfiability (SAT) solvers have been the subject of remarkable improvements since the mid 90s. One of the main reasons for these improvements has been the wide range of practical applications of SAT. Indeed, examples of modern applications of SAT range from termination analysis in term-rewrite systems to circuit-level prediction of crosstalk ...
openaire +1 more source
A New Cryptographic Scheme Utilizing the Difficulty of Big Boolean Satisfiability [PDF]
International Journal of Mathematical, Engineering and Management Sciences, 2018 A search problem may be identified as one, which requires an actual “search” for an answer or a solution. Such a problem may have no obvious method, which could be followed to determine a solution, other than to intelligently search through all candidate
Waleed Ahmad, Ali Muhammad Ali Rushdi
doaj +1 more source
Genetic Algorithm for Restricted Maximum k-Satisfiability in the Hopfield Network
International Journal of Interactive Multimedia and Artificial Intelligence, 2016 The restricted Maximum k-Satisfiability MAX- kSAT is an enhanced Boolean satisfiability counterpart that has attracted numerous amount of research. Genetic algorithm has been the prominent optimization heuristic algorithm to solve constraint optimization
Mohd Shareduwan Bin Mohd Kasihmuddin +2 more
doaj +1 more source