Problème de la somme de sous-ensembles

Le problème de la somme de sous-ensembles (en anglais : subset sum problem) est un problème de décision important en complexité algorithmique et en cryptologie. Le problème peut être décrit de la manière suivante : étant donné un ensemble $E$ de $n$ entiers, existe-t-il un sous-ensemble de $E$ dont la somme des éléments est nulle ? Par exemple, pour l'ensemble {-8, -3, -2, 4, 5}, la réponse est oui car la somme des éléments du sous-ensemble {-3, -2, 5} est nulle, par contre pour {-6, -1, 2, 3, 8} la réponse est non.

Le problème de la somme des sous-ensembles est NP-complet^[1], c'est-à-dire considéré comme difficile à résoudre efficacement par un algorithme. Il peut être vu comme un cas particulier du problème du sac à dos.

Variantes et problèmes liés

Avec une cible t

Le problème de la somme de sous-ensembles peut être décrit avec une cible entière $t$ :

Étant donné un ensemble $E$ de $n$ entiers, existe-t-il un sous-ensemble de $E$ dont la somme des éléments est $t$ ?

Problème de partition

Le problème de partition est un problème proche. Étant donné un ensemble $E$ de $n$ entiers, il faut décider si l'on peut partitionner $E$ en deux ensembles de même somme.

3SUM

Le problème 3SUM (en) est le suivant. Étant donné un ensemble $E$ de $n$ entiers, existe-t-il trois entiers dont la somme est nulle ?

Ce problème peut être résolu facilement par programmation dynamique en temps O(n²), mais il est conjecturé que cette complexité est optimale. De nombreux problèmes, notamment en géométrie algorithmique sont prouvés 3SUM-difficiles.

Complexité

Le problème de la somme de sous-ensembles est NP-complet^[1] : on peut par exemple lui réduire polynomialement le problème 3-SAT^[1]^,^[2].

Algorithmes

Algorithme exponentiel

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Algorithme pseudo-polynomial

Article détaillé : Algorithme pseudo-polynomial.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Algorithme d'approximation

Un algorithme d'approximation peut résoudre la version suivante du problème. Étant donné un ensemble E de N entiers et un entier s, retourner

oui, s'il y a un sous-ensemble de E dont la somme des éléments est s ;
non, s'il n'y a pas de sous-ensemble de E dont la somme des éléments est entre (1-c)s et s pour un petit c>0 ;
n'importe quoi, s'il y a un sous-ensemble de E dont la somme des éléments est entre (1-c)s et s, mais aucun dont la somme est s.

Si tous les nombres sont positifs ou nuls, la version approximative du problème de la somme de sous-ensembles se résout en temps polynomial en fonction de N et 1/c.

Notes et références

↑ ^{a b et c} Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition], «Problème de la somme de sous-ensemble», chap. 35.5, p. 1007
↑ Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne) pp. 83−85, preuve de la Proposition 3-AH

Bibliographie

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition]. Chapter 35.5, « The subset-sum problem ».
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, (ISBN 0-7167-1045-5).

Read other articles:

Albania

Republik AlbaniaRepublika e Shqipërisë (Albania) Bendera Lambang Semboyan: Ti Shqipëri, më jep nder, më jep emrin Shqipëtar (Albania: Kamu Albania, Berikan diriku kehormatan, Berikan diriku nama Albania)Lagu kebangsaan: Himni i Flamurit (Indonesia: Lagu himne untuk bendera) Perlihatkan BumiPerlihatkan peta EropaPerlihatkan peta BenderaLokasi Albania (hijau gelap)di Eropa (abu-abu)Ibu kota(dan kota terbesar)Tirana41°20′N 19°48′E / ...

Hu Yaobang

Hu Yaobang 胡耀邦 Sekretaris Jenderal Partai Komunis TiongkokMasa jabatan1980 – 1987 PendahuluKosong, terakhir dipegang oleh Deng XiaopingPenggantiZhao ZiyangKetua Partai Komunis TiongkokMasa jabatan1981 – 1982 PendahuluHua GuofengPenggantiPetahana Informasi pribadiLahir(1915-11-20)20 November 1915 Hunan, TiongkokMeninggal15 April 1989(1989-04-15) (umur 73) Beijing, TiongkokKebangsaanRepublik Rakyat TiongkokPartai politikPartai Komunis TiongkokSunting kotak info&...

Jack Steinberger

Jack Steinberger Jack Steinberger (lahir 25 Mei 1921) ialah seorang fisikawan. Ia adalah salah satu penemu muon neutrino. Ia memenangkan Hadiah Nobel Fisika pada 1988. Steinberger lahir di kota Bad Kissingen di Bayern, Jerman, tetapi meninggalkan kota itu pada usia 13, karena meningkatnya anti-Semitisme dari partai Nazi. Ia pindah ke Amerika Serikat, di mana ia tinggal selama beberapa tahun, sebelum pindah ke Swiss untuk bekerja di CERN. Pranala luar Otobiografi Diarsipkan 2005-03-03 di Wayba...

Crucifixion from Nové Sady (Master of the Rajhrad Altarpiece)

Crucifixion from Nové Sady, Master of the Rajhrad Altarpiece, National Gallery in Prague Crucifixion from Nové Sady, (also referred to as the Crucifixion of the Rajhrad Altarpiece, the Crucifixion of the Olomouc, Altar of the Holy Cross, or the Novosady panel) is part of a larger altar polyptych called the Rajhrad Altarpiece (around 1440). Its author is the last important personality of Czech panel painting of the pre-Hussite period, known as the Master of the Rajhrad Altarpiece. The painti...

Les Échos

Pour les articles homonymes, voir Les Échos (homonymie). Ne doit pas être confondu avec L'Écho. Les Échos Pays France Langue français Périodicité quotidien (lundi au vendredi) Format berlinois (2 cahiers) Genre presse économique et financière Prix au numéro 3,60 € en semaine[1], 6,00 € le numéro du vendredi-samedi Diffusion 139 877[2] ex. (2022) Fondateur Robert Servan-Schreiber Date de fondation 1908 (il y a 116 ans) Propriétaire Bernard Arnault via Groupe Les...

العلاقات الإثيوبية السنغافورية

العلاقات الإثيوبية السنغافورية إثيوبيا سنغافورة إثيوبيا سنغافورة تعديل مصدري - تعديل العلاقات الإثيوبية السنغافورية هي العلاقات الثنائية التي تجمع بين إثيوبيا وسنغافورة.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتي�...

Borgo Vercelli

Borgo Vercelli commune di Italia Tempat Negara berdaulatItaliaRegion di ItaliaPiedmontProvinsi di ItaliaProvinsi Vercelli NegaraItalia Ibu kotaBorgo Vercelli PendudukTotal2.256 (2023 )GeografiLuas wilayah19,3 km² [convert: unit tak dikenal]Ketinggian126 m Berbatasan denganCasalino Casalvolone Vercelli Villata Vinzaglio SejarahSanto pelindungMaria Diangkat ke Surga Informasi tambahanKode pos13012 Zona waktuUTC+1 UTC+2 Kode telepon0161 ID ISTAT002017 Kode kadaster ItaliaB046 Lain-la...

DTVPal

DTVPal logo The DTVPal was a line of digital-to-analog converter boxes designed by EchoStar Communications, under the Dish Network name. The boxes were marketed starting in 2008.[1] The units debuted to both love and criticism from purchasers, primarily related to reliability, warranty, and service issues.[2] All models in the line were discontinued. One model, the DTVPal DVR, had unique features in this class of product: the ability to pause live TV and time-shift broadcast T...

Videografi Daniel Padilla

Kathryn Bernardo tampil di video musik Nasa Iyo Na Ang Lahat and Simpleng Tuladmo Daniel Padilla, seorang aktor dan penyanyi Filipina telah membintangi beberapa video musik, dan tampil di beberapa iklan. Video musik Judul Tahun Artis lain Sutradara Deskripsi Ref. Sebagai Bintang Utama Prinsesea 2013 Tidak Ada Galileo Te [1][2] Nasa Iyo Na Ang Lahat Kathryn Bernardo Ateneo de Manila University Daniel digambarkan tengah berada di dalam kamar, bernyanyi sambil memainkan ukulele. ...

Hush Little Baby (novel)

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The topic of this article may not meet Wikipedia's notability guideline for books. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merge...

Mitsui & Co.

Japanese corporation Not to be confused with Mitsui Group. Mitsui & Co., Ltd. 三井物産株式会社Headquarters in Ōtemachi, Chiyoda, TokyoCompany typePublic (KK)Traded asTYO: 8031TOPIX Core 30 ComponentIndustryTrading CompaniesFoundedJuly 25, 1947; 76 years ago (1947-07-25)FounderTakashi Masuda, Tatsuzo MinakamiHeadquarters2-1, Otemachi 1-chome, Chiyoda-ku, Tokyo 100-8631, Japan, Tokyo, JapanArea served132 Offices in 64 Countries / Regions (2020)Key peopleTatsuo Yas...

LIV Golf

Professional golf league LIV GolfCurrent season, competition or edition: 2024 LIV Golf LeagueSportGolfFounded2021First season2022Owner(s)Public Investment FundCEOGreg NormanCountriesBased internationallyMost titlesTournament wins: Talor Gooch (3) Dustin Johnson (3) Brooks Koepka (3) Cameron Smith (3)TV partner(s) The CW (United States) Seven Network (Australia) LIV GOLF + (Worldwide) Official websitewww.livgolf.com LIV Golf (/lɪv/ LIV) is a professional men's golf tour. The name LIV refers t...

Cartier (entreprise)

Pour les articles homonymes, voir Cartier. Cartier Logo de Cartier. Boutique Cartier à Paris aux Champs-Élysées. Création 1847 à Paris Fondateurs Louis-François Cartier Personnages clés Louis Cartier Forme juridique Société par actions simplifiée Siège social Paris France Direction Cyrille Vigneron[1], président et CEO de Cartier International Activité Joaillerie, Horlogerie, Maroquinerie, Accessoires, Parfums. Société mère Compagnie Financière Richemont SA Effectif 883...

Mary Lambert (singer)

Mary LambertLambert in 2018BornMary Danielle Lambert (1989-05-03) May 3, 1989 (age 35)Seattle, Washington, U.S.Occupations Singer songwriter spoken word artist LGBTQ activist poet Years active2011–presentSpouse Wyatt Paige Hermansen (m. 2022; sep. 2024)Musical careerGenres R&B folk pop spoken word Instrument(s) Vocals piano guitar cello Labels Capitol Tender Heart[1][non-primary source needed][2][...

العلاقات الأوزبكستانية المولدوفية

العلاقات الأوزبكستانية المولدوفية أوزبكستان مولدوفا أوزبكستان مولدوفا تعديل مصدري - تعديل العلاقات الأوزبكستانية المولدوفية هي العلاقات الثنائية التي تجمع بين أوزبكستان ومولدوفا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعي...

2013年7月

<< 2013年 7月 >> 日一二三四五六 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 维基新闻国际/台湾/中国大陆逝世人物列表 7月1日亞奈爾山火。武裝衝突約15萬人於埃及各地發起示威活動以要求埃及總統穆罕默德·穆爾西辭職下台。《亞特蘭大（页面存档备份，存于互联网档案馆）》自從上周反政府示威遊行展開後，包含一名美國人在內的16人�...

Russian alphabet

Alphabet that uses letters from the Cyrillic script Russian Cyrillic alphabetРусская кириллическая азбукаScript type Alphabet Time period10th century (Old East Slavic) to present; modern orthography: 1918LanguagesRussianRelated scriptsParent systemsEgyptian hieroglyphs[1]Phoenician alphabetGreek alphabet (partly Glagolitic alphabet)Early Cyrillic alphabetRussian Cyrillic alphabetChild systemsMongolian Cyrillic alphabetISO 15924ISO 15924Cyrl (220), Ȁ...

Iharosberény

Village in Southern Transdanubia, HungaryIharosberény Beryn (in Latin) Berinja (in Croatian)VillageInkey Mansion in Iharosberény Coat of armsLocation of Somogy county in HungaryIharosberényLocation of IharosberényCoordinates: 46°21′59″N 17°06′40″E / 46.36627°N 17.11123°E / 46.36627; 17.11123Country HungaryRegionSouthern TransdanubiaCountySomogyDistrictCsurgóRC DioceseKaposvárArea • Total49.65 km2 (19.17 sq mi)Population...

Казаков, Юрий Павлович

В Википедии есть статьи о других людях с такой фамилией, см. Казаков; Казаков, Юрий. Юрий Павлович Казаков Дата рождения 8 августа 1927(1927-08-08) Место рождения Москва, СССР Дата смерти 29 ноября 1982(1982-11-29) (55 лет) Место смерти Москва, СССР Гражданство СССР Образование Литератур�...

Impact (film)

ImpactElla Raines, Brian Donlevy (1949)SutradaraArthur LubinProduserLeo C. PopkinSkenario Jay Dratler Dorothy Davenport CeritaJay DratlerPemeran Brian Donlevy Ella Raines Charles Coburn Helen Walker Penata musikMichel MicheletSinematograferErnest LaszloPenyuntingArthur H. NadelPerusahaanproduksiHarry Popkin ProductionsCardinal PicturesDistributorUnited ArtistsTanggal rilis 19 Maret 1949 (1949-03-19) (New York City) 1 April 1949 (1949-04-01) (Amerika Serikat) Durasi111 ...