按年被提到
20032015 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:cond-mat/0310317 · cond-mat.dis-nn

The Easiest Hard Problem: Number Partitioning

Stephan Mertens · 2003
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2015-08-07 · 最近 2019-10-27
2不同的人
2活跃月份
2讨论串
125被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论deepnet · 2015-08

“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”

The Easiest Hard Problem (2002)原评论 ↗
评论curuinor · 2019-10

“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 Partitioning"(https://arxiv.org/pdf/cond-mat/0310317.pdf). But it reduces to subset sum, …”

Show HN: Listen to an NP-Complete Problem原评论 ↗