Solving QSAT in sublinear depth

DOI10.1007/978-3-030-12797-8_13MaRDI QIDQ2328327zbMATH OpenOpenAlexFDO

Authors Alberto Leporati, Luca Manzoni, Antonio E. Porreca, Claudio Zandron, Giancarlo Mauri

Publication date 10 October 2019

Full work available at URL https://arxiv.org/abs/1902.03879

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Parametric quantified SAT solving
• Solving the resolution-free SAT problem by submodel propagation in linear time
• Solving satisfiability in less than \(2^ n\) steps
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Solving quantified constraint satisfaction problems
• Approximating satisfiable satisfiability problems
• scientific article; zbMATH DE number 2065279
• Incremental QBF solving by DepQBF
• Constant rate PCPs for circuit-SAT with sublinear query complexity

Cited in

(7)

• Characterizing PSPACE with shallow non-confluent P systems
• P systems attacking hard problems beyond NP: a survey
• A new method to simulate restricted variants of polarizationless P systems with active membranes
• Bounding the space in P systems with active membranes
• P systems with evolutional symport and membrane creation rules solving QSAT
• Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources
• Solving a PSPACE-complete problem with cP systems

This page was built for publication: Solving QSAT in sublinear depth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328327)