Subset sum problem
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice.
Wikipage disambiguates
3SUMComputer GoDynamic programmingElliptic curve only hashExponentiationGeneric-case complexityGlossary of artificial intelligenceIndex of combinatorics articlesKarp's 21 NP-complete problemsKnapsack (disambiguation)Knapsack problemList of NP-complete problemsList of algorithmsList of computability and complexity topicsList of group theory topicsList of knapsack problemsMaximum subarray problemMerkle–Hellman knapsack cryptosystemMultiway number partitioningNP-completenessNP-equivalentNP-hardnessNP (complexity)One-way functionOptical computingP versus NP problemPartition problemPillai sequencePostage stamp problemPseudopolynomial time number partitioningRado's theorem (Ramsey theory)Sartaj SahniSecurity of cryptographic hash functionsString theory landscapeSubsetSubset-sumSubset-sum problemSubset SumSubset sumSubset sums
Link from a Wikipage to another Wikipage
primaryTopic
Subset sum problem
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice.
has abstract
El problema de la suma de subc ...... al del problema de la mochila.
@es
Em ciência da computação, o pr ...... odos os elementos do conjunto.
@pt
Le problème de la somme de sou ...... lier du problème du sac à dos.
@fr
Problem sumy podzbioru - jeden ...... my wszystkich liczb ze zbioru.
@pl
The subset sum problem (SSP) i ...... e multiple subset sum problem.
@en
В інформатиці задача про суму ...... ляють швидко знайти відповідь.
@uk
Задача о сумме подмножеств — э ...... уммы всех элементов множества.
@ru
مسألة مجموع المجموعات الجزئية ...... سط المسائل من المسائل المعقدة.
@ar
子集和問題（英語：Subset sum problem），又 ...... 中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。
@zh
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論に ...... 解くことができる。（詳しくは、ナップサック問題の項を参照。）
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,026,313,674
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
hypernym
type
comment
El problema de la suma de subc ...... al del problema de la mochila.
@es
Em ciência da computação, o pr ...... ero. O problema é NP-completo.
@pt
Le problème de la somme de sou ...... , 2, 3, 8} la réponse est non.
@fr
Problem sumy podzbioru - jeden ...... astępującą definicje problemu:
@pl
The subset sum problem (SSP) i ...... easonably quickly in practice.
@en
В інформатиці задача про суму ...... елементів у множині (тобто, ).
@uk
Задача о сумме подмножеств — э ...... оль.Задача является NP-полной.
@ru
مسألة مجموع المجموعات الجزئية ...... سط المسائل من المسائل المعقدة.
@ar
子集和問題（英語：Subset sum problem），又 ...... 中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。
@zh
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論に ...... 解くことができる。（詳しくは、ナップサック問題の項を参照。）
@ja
label
Problem sumy podzbioru
@pl
Problema da soma dos subconjuntos
@pt
Problema de la suma de subconjuntos
@es
Problème de la somme de sous-ensembles
@fr
Subset sum problem
@en
Teilsummenproblem
@de
Задача о сумме подмножеств
@ru
Задача про суму підмножини
@uk
مسألة مجموع المجموعات الجزئية
@ar
子集和問題
@zh