On the complexity of the pancake problem
Fuxiang Yu · Mathematical logic quarterly · 2007
Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, calledthe 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. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)