5 papers · 1 filter
A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Andre Grosse, Joerg Rothe, Gerd Wechsung
We show that computing the lexicographically first four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove th…
Self-Specifying Machines
Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung
We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natu…
Query Order
Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung
We study the effect of query order on computational power, and show that $\pjk$-the languages computable via a polynomial-time machine given one query to the jth level of the boole…
Easy Sets and Hard Certificate Schemes
Lane A. Hemaspaandra, Joerg Rothe, Gerd Wechsung
Can easy sets only have easy certificate schemes? In this paper, we study the class of sets that, for all NP certificate schemes (i.e., NP machines), always have easy acceptance ce…
Robust Reductions
Jin-Yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
We continue the study of robust reductions initiated by Gavalda and Balcazar. In particular, a 1991 paper of Gavalda and Balcazar claimed an optimal separation between the power of…