On the Complexity of the Pancake Problem | Zendy

Fuxiang Yu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Complexity of the Pancake Problem

Author(s) -

Fuxiang Yu

Publication year - 2007

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2006.08.009

Subject(s) - mathematics , time complexity , set (abstract data type) , class (philosophy) , oracle , computational complexity theory , plane (geometry) , separable space , combinatorics , complexity class , polynomial , turing , discrete mathematics , algorithm , computer science , artificial intelligence , geometry , mathematical analysis , software engineering , programming language

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)

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research