𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the pancake problem

✍ Scribed by Fuxiang Yu

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
249 KB
Volume
53
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 SIMILAR VOLUMES

On the Diameter of the Pancake Network
On the Diameter of the Pancake Network
✍ Mohammad H. Heydari; I.Hal Sudborough 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 310 KB

The n-dimensional pancake network, P , has processors labeled with each of the n n! distinct permutations of length n and a connection between two processors when the label of one is obtained from the other by some prefix reversal. Each permutation is considered as a stack of different size pancakes

On the complex moment problem
On the complex moment problem
✍ Yurij M. Berezansky; Mykola E. Dudkin 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract The article is devoted to the solution of the infinite‐dimensional variant of the complex moment problem, and to the uniqueness of the solution. The main approach is illustrated for the best explanation on the one‐dimensional case. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

The average complexity of a coin-weighin
The average complexity of a coin-weighing problem
✍ L. Alonso; P. Chassaing; R. Schott 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 511 KB

Given a set of n coins, some of them weighing H , the others weighing h , h < H , we prove that to determine the set of heavy coins, an optimal algorithm requires an average of probabilities of being light and heavy. A simple quasi-optimal algorithm is described. Similar results are derived for th