Phase transitions of subset sum and Shannon's limit in source coding

被引：2

作者：

Sasamoto, T ^{[1
]}

机构：

[1] Tokyo Inst Technol, Dept Phys, Meguro Ku, Tokyo 1528551, Japan

来源：

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS | 2003年 / 321卷 / 1-2期

关键词：

NP-complete problems; phase transitions; Shannon's limit;

D O I：

10.1016/S0378-4371(03)00024-4

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We consider statistical properties of an NP-complete problem, the subset SLIM, using the methods and concepts of statistical mechanics. After introducing the statistical mechanical treatment of the problem, the phase transition behaviors are discussed. We also introduce a source coding scheme which is based on the idea of the subset SLIM. It is shown that the phase transitions in the subset sum is related to Shannon's limit for source coding. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：369 / 374

页数：6

共 10 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] Probabilistic analysis of the number partitioning problem [J].

Ferreira, FF ;

Fontanari, JF .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1998, 31 (15) :3417-3428

[3]

GENT IP, 1996, P IJCAI 99

[4]

HOGG T, 1996, FRONTIERS PROBLEM SO, V81

[5] Phase transition in the number partitioning problem [J].

Mertens, S .

PHYSICAL REVIEW LETTERS, 1998, 81 (20) :4281-4284

[6] Random costs in combinatorial optimization [J].

Mertens, S .

PHYSICAL REVIEW LETTERS, 2000, 84 (06) :1347-1350

[7] A physicist's approach to number partitioning [J].

Mertens, S .

THEORETICAL COMPUTER SCIENCE, 2001, 265 (1-2) :79-108

[8]

Mezard M., 1987, SPIN GLASS THEORY

[9]

Nishimori H., 2001, Statistical physics of spin glasses and information processing: an introduction

[10] Statistical mechanics of an NP-complete problem: subset sum [J].

Sasamoto, T ;

Toyoizumi, T ;

Nishimori, H .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2001, 34 (44) :9555-9567

← 1 →