Jump to ContentJump to Main Navigation
Computational Complexity and Statistical Physics$
Users without a subscription are not able to see the full content.

Allon Percus, Gabriel Istrate, and Cristopher Moore

Print publication date: 2005

Print ISBN-13: 9780195177374

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195177374.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 17 October 2021

The Easiest Hard Problem: Number Partitioning

The Easiest Hard Problem: Number Partitioning

Chapter:
Chapter 5 The Easiest Hard Problem: Number Partitioning
Source:
Computational Complexity and Statistical Physics
Author(s):

Stephan Mertens

Publisher:
Oxford University Press
DOI:10.1093/oso/9780195177374.003.0012

The number partitioning problem (NPP) is defined easily: Given a list a1, a2, . . . , an of positive integers, find a partition, that is, a subset A {1,..., n}, minimizing the discrepancy Number partitioning is of considerable importance, both practically and theoretically. Its practical applications range from multiprocessor scheduling and the minimization of VLSI circuit size and delay [102, 504], to public key cryptography [387], to choosing up sides in a ball game [237]. Number partitioning is also one of Garey and Johnson's six basic NP-hard problems that lie at the heart of the theory of NP-completeness [191, 388], and is in fact the only one of these problems that actually deals with numbers. Hence, it is often chosen as a base for NP-completeness proofs of other problems involving numbers, such as bin packing, multiprocessor scheduling [38], quadratic programming, and knapsack problems. The computational complexity of the NPP depends on the type of input numbers {a1, a2 , . . . , an}. Consider the case where the values of aj are positive integers bounded by a constant A. Then the discrepancy E can take on at most nA different values, so the size of the search space is O(nA) instead of O(2n) and it is straightforward to devise an algorithm that explores this reduced space in time polynomial in nA [191]. Of course, such an algorithm does not prove P = NP: a concise encoding of an instance requires O(nlog2 A) bits, and A is not bounded by any power of Iog2 A. This feature of the NPP is called pseudopoly nomiality. The NP-hardness of the NPP becomes apparent when input numbers are of a size exponentially large in n or, after division by the maximal input number, of exponentially high precision. To study typical properties of the NPP, the input numbers are often taken to be independent, identically distributed random variables. Under this probabilistic assumption, the minimal discrepancy E0 is a stochastic quantity.

Keywords:   central limit theorem, differencing heuristic, entropy, pseudo-polynomiality, random cost approximation, search tree, time complexity, traveling salesman problem

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .