𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of string folding

✍ Scribed by Mike Paterson; Teresa Przytycka

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
1001 KB
Volume
71
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

A fold of a finite string S over a given alphabet is an embedding of S in some fixed infinite grid, such as the square or cubic mesh. The score of a fold is the number of pairs of matching string symbols which are embedded at adjacent grid vertices. Folds of strings in two-and threedimensional meshes are considered, and the corresponding problems of optimizing the score or achieving a given target score are shown to be NP-hard.

πŸ“œ SIMILAR VOLUMES

Complexity of protein folding
Complexity of protein folding
✍ Aviezri S. Fraenkel πŸ“‚ Article πŸ“… 1993 πŸ› Springer 🌐 English βš– 719 KB

It is believed that the native folded three-dimensional conformation of a protein is its lowest free energy state, or one of its lowest. It is shown here that both a two-and three-dimensional mathematical model describing the folding process as a free energy minimization problem is NPhard. This mean

On the Comparison Complexity of the Stri
On the Comparison Complexity of the String Prefix-Matching Problem
✍ Dany Breslauer; Livio Colussi; Laura Toniolo πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 525 KB

In this paper we study the exact comparison complexity of the string prefixmatching problem in the deterministic sequential comparison model with equality tests. We derive almost tight lower and upper bounds on the number of symbol comparisons required in the worst case by on-line prefix-matching al