enter search term and/or author name
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following...
If the class TAUT of tautologies of propositional logic has no almost optimal algorithm, then every algorithm A deciding TAUT has a hard sequence, that is, a polynomial time computable sequence witnessing that A is not almost optimal. We show that...
The Complexity of Approximately Counting Tree Homomorphisms
Leslie Ann Goldberg, Mark Jerrum
Article No.: 8
We study two computational problems, parameterised by a fixed tree H. #HOMSTO(H) is the problem of counting homomorphisms from an input graph G to H. #WHOMSTO(H) is the problem of counting weighted...
A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Article No.: 9
The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division...