11 citations · 18 across the 4 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2004★ 1 cited
Isomorphic Implication
Michael Bauland, Edith Hemaspaandra
We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set…
cs.CC2004
All Superlinear Inverse Schemes are coNP-Hard
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diago…
cs.CC2004★ 11 cited
Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas
Edith Hemaspaandra
In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems, showed that a…