
	Where results make sense

Topic: Subset sum problem

Related Topics

Knapsack problem

Boolean satisfiability problem

Clique problem

Hamiltonian cycle problem

Subgraph isomorphism problem

Quadratic programming

Fifteen puzzle

NP (complexity)

In the News (Sun 8 Nov 09)

Northern Trust

Marvin Harrison

Peter Chernin

Gary Locke

Match Play

Penelope Cruz

Mickey Rourke

AR Rahman

Danny Boyle

Hugh Jackman

	Introduction
		Both the Brickell and Lagarias-Odlyzko algorithms reduce the subset sum problem to that of finding a short vector in a lattice.
		Therefore it seems worthwhile to separate the issues of efficiency of lattice basis reduction algorithms from the question of how well the subset sum problem can be reduced to that of finding a short vector in a lattice.
		In this note we analyze a simple modification of the part of the Lagarias-Odlyzko algorithm that reduces the subset sum problem to a short vector in a lattice problem.
	www.farcaster.com /papers/crypto-sumalg/node1.html (772 words)

	Subset sum problem
		The subset sum problem is an important problem in complexity theory and cryptography.
		Subset sum can also be thought of as a special case of the knapsack problem.
		Although the subset sum problem is a decision problem, the cases when an approximate solution is sufficient have also been studied, in the field of approximation algorithms.
	www.brainyencyclopedia.com /encyclopedia/s/su/subset_sum_problem.html (1414 words)

	NationMaster - Encyclopedia: Subset sum problem
		One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.
		Although the subset sum problem is a decision problem, the cases when an approximate solution is sufficient have also been studied, in the field of approximation algorithms.
		The subset sum problem is the inverse of this, that is, given an integer T, is there a subset of S whose sum is T? This decision problem (requiring only a yes-no response) is an NP-complete problem.
	www.nationmaster.com /encyclopedia/Subset-sum-problem (2055 words)

	Subset-sum problems are hard
		A seemingly simpler problem is the subset-sum decision problem.
		We show that one problem is as difficult as another by showing that a method of solving the supposedly easier problem can be used to solve another problem.
		The important point is that they are all well-known problems for which many people have been unable to find efficient solution methods, which makes it unlikely that there is a method which solves all subset-sum decision problems efficiently (we will go into more detail on this in section 5).
	www.math.sunysb.edu /~scott/blair/Subset_sum_problems_are.html (361 words)

	Intelligent Drone » Archive » Thoughts on the Subset Sum Problem (P vs. NP) (Site not responding. Last check: )
		Probably the simplest NP-complete problem to describe is the ‘subset sum problem’.
		Stated differently, it is possible to solve the subset sum problem using waves.
		Problems of this type are said to be “weakly NP-complete”;, to contrast them with problems like Travelling Salesman that are “strongly NP-complete”;.
	idrone.net /2006/06/11/thoughts-on-the-subset-sum-problem-p-vs-np (2482 words)

	NP-complete: Definition and Links by Encyclopedian.com
		In complexity theory, the complexity class NP-complete is the set of problems that are the hardest problems in NP, in the sense that they are the ones most likely not to be in P.
		One example of an NP-complete problem is the subset sum problem which is: given a finite set of integers, determine whether any nonempty subset of them adds up to zero.
		The Graph Isomorphism problem is suspected to be neither in P nor NP-complete, though it is obviously in NP.
	www.encyclopedian.com /np/NP-complete-problems.html (986 words)

	subset sum problem (Site not responding. Last check: )
		The subset sum problem is an important problem in complexity theory and cryptography.
		Subset sum can also be thought of as a special case of the knapsack problem.
		What makes the problem difficult is that the number of binary place values it takes to state the problem needs to be equal to the number of decision variables in the problem.
	www.wapipedia.org /wikipedia/mobiletopic.aspx?cur_title=subset_sum_problem (701 words)

	Subset sum problem
		This means that having a polynomial time algorithm for Subset Sum also allows, given an infeasible instance, to prove that it is not feasible in polynomial time.
		There are several ways to solve subset sum in time exponential in N. The most naive algorithm would be to cycle through all subsets of N numbers and, for every one of them, check if the subset sums to the right number.
		For example, the problem could be: given an integer n and a set of integers in the range [0, n − 1], does any subset sum to zero modulo n?
	www.xasa.com /wiki/en/wikipedia/s/su/subset_sum_problem.html (1501 words)

	M5410 Merkle-Hellman Knapsack Cryptosystem
		The underlying mathematical problem is the subset sum problem which is closely related to the more famous knapsack problem of operations research (thus, the "knapsack" in the name of this system is a misnomer).
		The subset sum problem is the inverse of this, that is, given an integer T, is there a subset of S whose sum is T? This decision problem (requiring only a yes-no response) is an NP-complete problem.
		For example, to decide if T is a subset sum of the super-increasing set 3, 7, 12, 30, 60, 115, we start by finding the largest value in the set that is less than or equal to T, subtract this value from T to form T' and then repeat the process for T'.
	www-math.cudenver.edu /~wcherowi/courses/m5410/ctcknap.html (959 words)

	[No title]
		In this work, finite sums were calculated to confirm the convergence of infinite sums and measure the coverage of the integers by the predecessor tree.
		In this work, the infinite summations of the densities of integers in various disjoint subsets converge to finite values which measure various aspects of the coverage of the integers by the predecessor tree.
		In the Collatz 3n+1 problem, the value in the root node is 1.
	www-personal.ksu.edu /~kconrow/glossary.html (2014 words)

	[No title] (Site not responding. Last check: )
		Suppose we find a subset C of V and E' of E such that \sum_{i \in C} ai + \sum_{(i,j) \in E'} b_ij = k' First, note that we never have a carry in the E less significant digits; operations are base 4, and there are at most 3 ones in each column.
		Subset Sum is a special case of the Knapsack problem.
		An instance of the Subset Sum has integers a1,...,an, and a parameter k, and the goal is to decide if there is a subset of integers that sum to exactly k.
	www.cs.ucsb.edu /~suri/cs130b/NPC-3.txt (681 words)

	[No title]
		This subset was created using a search strategy that includes terms in the Alternative Medicine branch of MeSH, terms provided by NCCAM, and a number of journals indexed for MEDLINE that include significant CAM-related content.
		It is intriguing to think that this subset may correspond with that proportion of parietal cells that derive from the pre-neck lineage.
		With Dueling Devotions, Subset ride the tenuous line of writing catchy, intelligent pop songs without resorting to the emotional bleeting or lyrical patronization that is so prevalent in the genre.
	www.lycos.com /info/subset.html (571 words)

	Optimal Measurements for the Dihedral Hidden Subgroup Problem
		We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.
		We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.
		In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
	www.santafe.edu /research/publications/wpabstract/200504013 (235 words)

	4.5.1 Subset Sum Problem
		The functional problem of a knapsack vector A together with a sum s is denoted by (A, s).
		The corresponding subset is A' = (15, 22, 16).
		The decision problem and the functional problem are equivalent with respect to the complexity meaning if a polynomial algorithm is known solving the decision problem, this algorithm can also be used for solving the functional problem and vice versa.
	www-fs.informatik.uni-tuebingen.de /~reinhard/krypto/English/4.5.1.e.html (561 words)

	Lecture 14 (Site not responding. Last check: )
		We wanted to cover the subset sum problem, traveling salesman and analysis of greedy set cover, Max 3-sat problem and some approximation algorithms problem.
		The proof involves the bound on the sum from the elements that were removed from the list.
		We reduce the Hamiltonian cycle problem to the approximate Traveling Salesman Problem.
	www.cs.rpi.edu /~moorthy/Courses/DA/Lectures/Lec14.html (296 words)

	308-506 Lecture Notes: 2 October 2001
		We prove (usually easily) that B is in NP, take a known NP-complete problem A, and reduce A to B. The power of this method depends in part on the comprehensiveness of our library of known NP-complete problems, then, and in part on our facility in designing reductions.
		Given the k items with sum s, and the target t, we can add one new item b of size s-2t if this is positive, or 2t-s if that is positive.
		The fields themselves must be large enough that no sum of the numbers can have a carry from one field to another -- (log m) +1 will suffice as at most m 1's in a single field will ever be added.
	www.cs.mcgill.ca /~barring/notes/8.htm (1980 words)

Try your search on: Qwika (all wikis)