Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with cause:
TR12-069 | 23rd March 2012
Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

On the complexity of computing minimal unsatisfiable LTL formulas

We show that (1) the Minimal False QCNF search problem (MF-search) and
the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ... more >>>

ISSN 1433-8092 | Imprint