Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Entropy-based analysis of the number partitioning problem.

A R Lima1, M Argollo de Menezes

  • 1Laboratoire de Physique et Méchanique des Milieux Hétérogènes, ESPCI Paris, 10 rue Vauquelin, 75231 Paris Cedex 05, France. arlima@if.uff.br

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|April 20, 2001
PubMed
Summary

This study applies statistical physics methods to the number partitioning problem (NPP), revealing key differences in spectral degeneracy for generalized versions. These findings may explain the difficulty in solving complex NPP instances.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Photoinactivation of Aedes aegypti larvae using riboflavin as photosensitizer.

Photodiagnosis and photodynamic therapy·2022
Same author

Photodynamic control of Aedes aegypti larvae with environmentally-friendly tetra-platinated porphyrin.

Journal of photochemistry and photobiology. B, Biology·2021
Same author

Proteomic profile of root canal contents in teeth with post-treatment endodontic disease.

International endodontic journal·2018
Same author

Reconstructive dosimetry for cutaneous radiation syndrome.

Brazilian journal of medical and biological research = Revista brasileira de pesquisas medicas e biologicas·2015
Same author

Morphological and Morphometric Description of Female Reproductive Tract of Sapajus apella (Capuchin monkey).

Anatomia, histologia, embryologia·2014
Same author

Anatomic study of the collateral branches of the abdominal aorta of primate species Saguinus niger.

Anatomia, histologia, embryologia·2014

Area of Science:

  • Statistical Physics
  • Computer Science
  • Computational Complexity

Background:

  • The number partitioning problem (NPP) is a fundamental NP-hard problem.
  • NPP can be mapped to a spin-glass problem, allowing for physics-based approaches.
  • Understanding the solution landscape is crucial for tackling NP-hard problems.

Purpose of the Study:

  • To apply the multicanonical method from statistical physics to the NPP.
  • To investigate the spectral degeneracy of NPP and its variations.
  • To analyze the impact of generalizing NPP to Q partitions on solution complexity.

Main Methods:

  • Utilizing the multicanonical simulation method.
  • Computing spectral degeneracy to quantify solution counts for specific costs and cardinality differences.

Related Experiment Videos

  • Examining an extension of NPP for Q partitions (Q>2).

    • Main Results:

    • The spectral degeneracy was computed for the NPP, providing insights into solution distribution.
    • A fundamental difference in spectral degeneracy was identified for the generalized NPP with Q>2 partitions.
    • This difference in degeneracy offers a potential explanation for the computational difficulty of generalized NPP.

    Conclusions:

    • The multicanonical method is a viable approach for studying the NPP.
    • Generalized number partitioning problems (Q>2) exhibit distinct spectral degeneracy characteristics.
    • The observed differences in spectral degeneracy may underlie the inherent difficulty in finding optimal solutions for generalized NPPs.