Publisher Summary The past few years have seen enormous progress in the performance of Boolean satisfiability (SAT) solvers. Despite the worst-case exponential run time of all known …
Description logics (DLs) have a long tradition in computer science and knowledge representation, being designed so that domain knowledge can be described and so that …
Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern algorithm design and analysis, with a broad range of theoretical and practical aspects that …
This newly expanded and updated second edition of the best-selling classic continues to take the" mystery" out of designing algorithms, and analyzing their efficacy and efficiency …
TJ Schaefer - Proceedings of the tenth annual ACM symposium on …, 1978 - dl.acm.org
The problem of deciding whether a given propositional formula in conjunctive normal form is satisfiable has been widely studied. I t is known that, when restricted to formulas having only …
Many different methods have been devised for automatically verifying finite state systems by examining state-graph models of system behavior. These methods all depend on decision …
We investigate the complexity of the classical problem of optimal policy computation in Markov decision processes. All three variants of the problem (finite horizon, infinite horizon …
Among the many approaches to formal reasoning about programs, Dynamic Logic enjoys the singulax aclv~ ntage of being strongly related to classical logic. Its variants constitute …
ACDHJ Hartmanis, T Henzinger, JHNJT Leighton… - 2006 - Springer
Classical complexity theory analyzes and classifies problems by the amount of a resource, usually time or space, that is required by algorithms solving them. It was a fundamental idea …