𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the identification problem in Hamming spaces

✍ Scribed by Iiro Honkala; Antoine Lobstein

Publisher
Springer-Verlag
Year
2002
Tongue
English
Weight
120 KB
Volume
38
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## 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 resul

On the complexity of recursion in proble
On the complexity of recursion in problem-solving
✍ M.C. Er πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science βš– 426 KB

The importance of paying attention to the complexity of recursion in problem solving is stressed. Many ill-founded beliefs and doctrines on constructing recursive algorithms are challenged. The Tower of Hanoi problem and its variant are used as concrete examples for illustrating that many seemingly

On the complexity of the car sequencing
On the complexity of the car sequencing problem
✍ TamΓ‘s Kis πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 190 KB

In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a su cient condition of membership of NP. We also provide a ps