Abstract

We study the computational complexity of finding a line that bisects simultaneously two sets in the two-dimensional plane, called the pancake problem, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main results are: (1) The complexity of bisecting a nice (thick) polynomial-time approximable set at a given direction can be characterized by the counting class #P. (2) The complexity of bisecting simultaneously two linearly separable nice (thick) polynomial-time approximable sets can be characterized by the counting class #P. (3) For either of these two problems, without the thickness condition and the linear separability condition (for the two-set case), it is arbitrarily hard to compute the bisector, even if it is unique