HackerPapers

arXiv:cond-mat/0310317cond-mat.dis-nn

The Easiest Hard Problem: Number Partitioning

Stephan Mertens

Abstract

Number partitioning is one of the classical NP-hard problems of combinatorial optimization. It has applications in areas like public key encryption and task scheduling. The random version of number partitioning has an "easy-hard" phase transition similar to the phase transitions observed in other combinatorial problems like $k$-SAT. In contrast to most other problems, number partitioning is simple enough to obtain detailled and rigorous results on the "hard" and "easy" phase and the transition that separates them. We review the known results on random integer partitioning, give a very simple derivation of the phase transition and discuss the algorithmic implications of both phases.

arXiv comments
8 pages, to appear in A.G. Percus, G. Istrate and C. Moore, eds., Computational Complexity and Statistical Physics (Oxford University Press, New York, 2004)
Journal reference
DOI
Subjects
cond-mat.dis-nnDisordered Systems and Neural Networks cond-mat.stat-mechStatistical Mechanics

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Aug 2015 to Oct 2019.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Show HN: Listen to an NP-Complete Problem 1 comment

    • Number partition, if you present it to someone who isn't familiar with it, is probably the easiest sounding NP-complete problem. In practice, it's definitely one of the easiest ones for practical applications. There' a paper entitled "The Easiest Hard Problem: Number…

      curuinorView on HNParent context

  2. The Easiest Hard Problem (2002) 1 comment

    • Stephen Mertens Paper * The Easiest Hard Problem: Number Partitioning* is a good review paper of the subject covering the phase transition between P and NP this problem exhibits and extending it to k-partitions. http://arxiv.org/abs/cond-mat/0310317

      deepnetView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.