×

Model-equivalent reductions. (English) Zbl 1128.68360

Bacchus, Fahiem (ed.) et al., Theory and applications of satisfiability testing. 8th international conference, SAT 2005, St Andrews, UK, June 19–23, 2005. Proceedings. Berlin: Springer (ISBN 3-540-26276-8/pbk). Lecture Notes in Computer Science 3569, 355-370 (2005).
Summary: In this paper, the notions of polynomial-time model equivalent reduction and polynomial-space model equivalent reduction are introduced in order to investigate in a subtle way the expressive power of different theories. We compare according to these notions some classes of propositional formulas and quantified Boolean formulas. Our results show that classes of theories with the same complexity might have different representation strength under some conjectures which are widely believed to be true in computational complexity theory.
For the entire collection see [Zbl 1077.68002].

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03B35 Mechanization of proofs and logical operations
03D15 Complexity of computation (including implicit computational complexity)

Software:

ASSAT
PDFBibTeX XMLCite
Full Text: DOI