𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of the generalized Lloyd - Max problem (Corresp.)

✍ Scribed by Garey, M.; Johnson, D.; Witsenhausen, H.

Book ID
114635150
Publisher
IEEE
Year
1982
Tongue
English
Weight
351 KB
Volume
28
Category
Article
ISSN
0018-9448

No coin nor oath required. For personal study only.

✦ Synopsis

However this method requires considering in turn each of the m ( 1 k possible choices of B. Thus when, e.g., one has II = m = 2 k, the effort required increases exponentially with k. A~wwr-A simple (combinatorial) special case of the generalized Lloyd-Max (or quantization) problem is shown to be nondeterministic polynomial (NP)-complete. A forfiori, the general problem of communication theory, in its combinatorial forms, has at least that complexity.

πŸ“œ SIMILAR VOLUMES

Complexity of the generalized conjugacy
Complexity of the generalized conjugacy problem
✍ Sang Geun Hahn; Eonkyung Lee; Je Hong Park πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 100 KB

Recently, the generalized conjugacy problem(GCP) in braid groups was introduced as a candidate for cryptographic one-way function. A GCP in a braid group can be transformed into a GCP in a general linear group by the Burau representation. We study the latter problem induced in this way.