کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
424419 | 685443 | 2007 | 21 صفحه PDF | دانلود رایگان |
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; and (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).
Journal: Electronic Notes in Theoretical Computer Science - Volume 167, 24 January 2007, Pages 95-115