Statistical Mechanics of an NP-complete Problem: Subset Sum

Simple item page
dc.creatorSasamoto, T.
dc.creatorToyoizumi, T.
dc.creatorNishimori, H.
dc.date2001-06-07
dc.date2001-06-18
dc.date.accessioned2026-07-07T02:41:40Z
dc.date.available2026-07-07T02:41:40Z
dc.descriptionWe study statistical properties of an NP-complete problem, the subset sum, using the methods and concepts of statistical mechanics. The problem is a generalization of the number partitioning problem, which is also an NP-complete problem and has been studied in the physics literature. The asymptotic expressions for the number of solutions are obtained. These results applied to the number partitioning problem as a special case are compared with those which were previously obtained by a different method. We discuss the limit of applicability of the techniques of statistical mechanics to the present problem.
dc.description17 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/cond-mat/0106125
dc.identifierhttp://arxiv.org/abs/cond-mat/0106125
dc.identifierJ. Phys. A: Math. Gen. 34 (2001) 9555-9567
dc.identifierdoi:10.1088/0305-4470/34/44/314
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/17835
dc.subjectStatistical Mechanics
dc.subjectDisordered Systems and Neural Networks
dc.titleStatistical Mechanics of an NP-complete Problem: Subset Sum
dc.typetext

Files

Collections

arXiv