Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with backbone:
TR14-031 | 16th February 2014
Joao Marques-Silva, Mikolas Janota

On the Query Complexity of Selecting Few Minimal Sets

Propositional Satisfiability (SAT) solvers are routinely used for
solving many function problems.

A natural question that has seldom been addressed is: what is the
best worst-case number of calls to a SAT solver for solving some
target function problem?

This paper develops tighter upper bounds on the query complexity of
more >>>

ISSN 1433-8092 | Imprint