Problema de la suma de subconjuntos

El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero? Por ejemplo, dado el conjunto { −7, −3, −2, 5, 8}, la respuesta es SI, porque el subconjunto { −3, −2, 5} suma cero. Este problema es NP-completo.

Un problema equivalente es: dado un conjunto de enteros y un entero s, ¿existe algún subconjunto cuya suma sea s? La suma de subconjuntos también puede verse como un caso especial del problema de la mochila.

Discusión general

El problema de la suma de subconjuntos es una buena introducción a los problemas NP-completos por dos razones:

La mayoría de los problemas físicos pueden ser resueltos con un índice de error del +/- 1%. Resolver un problema de suma de subconjuntos para 100 enteros con una precisión de +/-10-100 puede parecer irrelevante, pero no lo es por dos razones.

Primero, el problema de la suma de subconjuntos tiene una declaración precisa de la complejidad lógica de una clase de problemas (los NP-completos). Resolverlo exactamente significaría resolver todos los problemas en esta clase. Resolverlo con un margen de error de +/- 1% volvería inútil al algoritmo para algunos otros problemas. Segundo, en cuando menos un contexto, es de hecho importante resolver el problema de la suma de subconjuntos de manera exacta. En criptografía, este problema surge cuando un asaltacódigos trata de deducir la llave secreta a partir de un mensaje y su versión cifrada. Una llave a una distancia de +/- 1% de la real es inservible.

Los casos en los que la solución aproximada es más que suficiente ya han sido estudiados, en el campo de los algoritmos de aproximación. Uno de esos algoritmos es tratado más adelante.

Resolución

Puede considerarse que la complejidad de la resolución del problema depende de dos parámetros:

  • N, el número de variables de decisión
  • P, la precisión del problema, el número de valores de posiciones binaria que toma definir el problema.

La complejidad de los algoritmos más conocidos es exponencial en el más pequeño de los dos parámetros N y P. Por tanto, el problema es más difícil si N y P son del mismo orden pero solo se vuelve más fácil si alguno de los dos se vuelve muy pequeño.

La imposición de ciertas restricciones sobre la secuencia de enteros sobre la que se opera, problema de la mochila simple, hacen que la resolución del problema sea trivial siguiendo un algoritmo definido. Este tipo de problemas es muy usado en criptografía.

Algoritmo de tiempo exponencial

Hay varias maneras de resolver la suma de subconjuntos en tiempo exponencial sobre N. El algoritmo más simplista verificaría todos los posibles subconjuntos de N y, para cada uno de ellos, compararía la suma al total buscado. El tiempo de ejecución es de orden O(2NN), dado que hay 2N subconjuntos y, para verificar cada subconjunto, tenemos que sumar N elementos.

Se conoce un mejor algoritmo de tiempo exponencial, que corre en tiempo de orden O(2N/2N). El algoritmo parte los N elementos en dos conjuntos de N/2 elementos cada uno. Para cada conjunto, calcula la suma de todos los 2N/2 posibles subconjuntos y las almacena en un vector de longitud 2N/2. Entonces ordena estos dos vectores, lo que se puede hacer en tiempo O(2N/2N). Una vez que los vectores están ordenados, el algoritmo puede verificar si un elemento del primer vector más un elemento del segundo dan el total s buscado en tiempo O(2N/2). Para hacer esto, el algoritmo pasa por el primer vector en orden decreciente (empezando en el elemento más grande) y por el segundo en orden creciente (empezando por el más pequeño). Cuando la suma del elemento en turno de los dos vectores es mayor que s, el algoritmo se mueve al siguiente elemento en el primer vector, cuando es menor que s se mueve al siguiente elemento en el segundo vector. Si se encuentra s el algoritmo termina.

Resolución dinámica de tiempo seudo-polinomial

El problema también puede ser resuelto como sigue, utilizando programación dinámica. Supongamos que la secuencia de enteros está representada por

x1,..., xn

y queremos encontrar un subconjunto cuya suma sea 0. Representemos ´la suma de valores negativos con N y la suma de valores positivos con P. Definamos la función booleana

Q(i, s)

como (verdadera o falsa) de

"existe un subconjunto de x1,..., xi cuya suma es s".

(Por tanto, el valor que realmente buscamos es Q(n,0).)

Es claro que

Q(i, s) = falso

si s<N o s>P.

Crear una matriz para guardar los valores de Q(i, s) para 1≤i≤n y N≤s≤P. La matriz puede ser llenada con una recursión simple.

Q(1,s) = "s=0 or x1=s".

Para i>1,

Q(i, s) = Q(i-1,s) o Q(i-1,s-xi).

El número total de operaciones aritméticas es

O(n(P - N)).

Por ejemplo, si todos los valores son

O(nk)

para algún k, entonces el tiempo requerido es

O(nk+1).

Esta solución no cuenta como de tiempo polinomial en teoría de complejidad porque P-N no es polinomial en el tamaño del problema, que es el número de bits usados para representarlo.

Algoritmo de aproximación en tiempo polinómico

Una versión aproximada de la suma de subconjuntos sería: dado un conjunto de números N

x1, x2,..., xN 

y un número s, regresar

  • si, cuando existe un subconjunto que sume s;
  • no, si no existe un subconjunto que sume algún total entre (1-c)s y s para algún c>0 pequeño;
  • cualquier respuesta, si algún subconjunto suma algún total entre (1-c)s y s pero ninguno suma s.

Si todos los números son no negativos, la suma de subconjuntos aproximada es soluble en tiempo polinómico para N y 1/c.

Referencias

  1. T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001. Chapter 35.5, The subset-sum problem.
  2. Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, W.H. Freeman. ISBN 0716710455 A3.2: SP13, pg.223.

Read other articles:

الجامعة الوطنية الخاصة معلومات التأسيس 2007[1]  الموقع الجغرافي إحداثيات 34°58′10″N 36°45′06″E / 34.96930556°N 36.75169444°E / 34.96930556; 36.75169444  البلد سوريا  إحصاءات الموقع الموقع الرسمي  تعديل مصدري - تعديل   الجامعة الوطنية الخاصة، هي جامعة خاصة في سوريا تأسست في ال

 

ILS Institut für Lernsysteme GmbH Logo Rechtsform Gesellschaft mit beschränkter Haftung Gründung 1977 Sitz Hamburg-Rahlstedt Leitung Ingo Karsten Martin Kurz Branche Aus- und Weiterbildung Website www.ils.de Das Institut für Lernsysteme (ILS) ist eine deutsche Fernschule mit Sitz in Hamburg. Sie wurde 1977 von Bertelsmann gegründet und gehört seit 1997 zur Klett Gruppe.[1] Das ILS ist mit jährlich etwa 80.000 Kunden der größte Vertreter der Branche.[2][3] Inha...

 

Taenga Coordenadas: 16° 22' S 143° 07' 59 O Geografia física País Polinésia Francesa Arquipélago Tuamotu Gambier Área 20  km² Geografia humana População 124 (2012)[1] Densidade 6,2  hab./km² Taenga é uma das ilhas do arquipélago de Tuamotu-Gambier, pertencente ao Taiti.[2][3] Referências ↑ Population des communes de Polynésie française en 2012 sur le site de l'Institut de la statistique de la Polynésie française (ISPF). ↑ (em inglês) The Lost I...

Esercito della SalvezzaBandiera dell'Esercito della SalvezzaClassificazionecristiana Orientamentometodista, movimento di Santità FondatoreWilliam BoothCatherine Mumford Fondata1865Londra AssociazioneOrdine della Stella d'Argento, Unione Femminile, Azione Mano Aperta, Associazione Salutista Italiana Personale Ospedaliero Diffusionemondiale Sede101 Newington Causeway, London, SE1 6BN Forma di governoteocratico Struttura organizzativamilitare Fedeli18.500 Congregazioni15.409 Membri1.150.666[...

 

Ця стаття є частиною Проєкту:Тернопільщина (рівень: 2, важливість: висока) Портал «Тернопільщина»Мета проєкту — створення якісних та інформативних статей на теми, пов'язані з Тернопільщиною. Ви можете покращити цю статтю, відредагувавши її, а на сторінці проєкту вказано, ч

 

ويلان سيبريان   معلومات شخصية الميلاد 28 يناير 1995 (28 سنة)[1]  لزابيم  الطول 1.81 م (5 قدم 11 1⁄2 بوصة) مركز اللعب وسط الجنسية فرنسا  معلومات النادي النادي الحالي سيون الرقم 10 مسيرة الشباب سنوات فريق 2006–2008 باريس 2008–2012 لانس المسيرة الاحترافية1 سنوات فريق م. (

Проєкт технічної допомоги Європейського Союзу (ЄС) «Гармонізація системи державних закупівель в Україні зі стандартами ЄС»  (англ. Harmonisation of public procurement system of Ukraine with EU standards) розпочав роботу 11 листопада 2013 року і був завершений у листопаді 2017 року. Проєкт фінансується ЄС ...

 

SunriseAlbum studio karya Pongki BarataDirilis2011Direkam2010-2011GenrePopLabelNagaswaraKronologi Pongki Barata -String Module Error: Match not foundString Module Error: Match not found Sunrise(2011) Pongki Barata Meets The Stars(2014)Pongki Barata Meets The Stars2014 Sunrise adalah album solo pertama karya Pongki Barata yang dirilis pada tahun 2011. Berisi 8 buah lagu dengan lagu Aku Milikmu (Malam Ini) sebagai lagu utama album ini. Daftar lagu Kau Selalu Aku Milikmu (Malam Ini) I Miss Y...

 

Irish rugby team For the newspaper, see Cork Constitution (newspaper). This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Cork Constitution – news · newspapers · books · scholar · JSTOR (April 2008) (Learn how and when to remove this template message) Rugby teamCork ConstitutionFull nameCork Constitution Football ClubUnionIRFUBranchMunsterNickname(s)ConFou...

El reino de Dios está en vosotros de León Tolstói Portada de la primera edición en español (2010)Género EnsayoTema(s) Religión, Anarquismo cristianoEdición original en rusoTítulo original Царство Божие внутри васCiudad Berlín Edición traducida al españolTraducido por Joaquín Fernández-Valdés RoigEditorial KairósPaís RusiaFecha de publicación 1894Páginas 420SerieIglesia y EstadoEl reino de Dios está en vosotrosEl padre Sergio[editar datos en W...

 

Lokasi Gunung Sinai di Semenanjung Sinai. Gregorius dari Sinai adalah seorang teolog abad ke-13.[1][2] Ia lahir sekitar tahun 1265 di dekat Klazomenai, daerah pantai barat Asia Kecil.[2] Di waktu muda, ia ditangkap dalam sebuah serangan dari bangsa Turki.[2] Setelah dibebaskan, ia pergi ke Siprus dan belajar hidup membiara di sana.[2] Setelah itu ia pergi ke Gunung Sinai dan memulai hidup membiaranya dengan penuh.[2] Ia lalu berkelana ke Kreta s...

 

Buaya nil Status konservasi Risiko Rendah Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Sauropsida Ordo: Crocodilia Famili: Crocodylidae Subfamili: Crocodylinae Genus: Crocodylus Spesies: C. niloticus Nama binomial Crocodylus niloticus(Laurenti, 1768) Buaya nil (bahasa Latin: Crocodylus niloticus) adalah salah satu dari empat spesies buaya yang dapat ditemui di Afrika dan spesies buaya terbesar kedua. Buaya nil dapat ditemui di kebanyakan Afrika dan pulau Madagaskar. B...

Цукрова хижа, де кленовий сік виварюється до стану сиропу Кленоварня, також цукрова хижа (фр. cabane à sucre), будиночок для соку, цукрова хатина або цукрова каюта — вид напівкомерційного підприємства, в основному поширений в Східній Канаді і північній частині Нової Англії. ...

 

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: West Mall – news · newspapers · books · scholar · JSTOR (January 2018) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: West Mall – ne...

 

Partai Demokrat Botswana Ketua umumIan KhamaKetua umumDaniel KwelagobeKantor pusatGaborone, Distrik TenggaraIdeologiKonservatismePosisi politikSayap kananParlemen Botswana37 / 57 Parlemen Pan Afrika3 / 5 BenderaSitus webBotswana Democratic Party (BDP) Partai Demokratik Botswana adalah partai konservatif yang memerintah di Botswana. Ketuanya adalah Dr. Ponatshego Kedikilwe. Ketua partai sebelumnya antara lain, Daniel Kwelagobe, Samson Guma Moyo, dan Letnan Jenderal Ian Khama. Lihat juga D...

District courts in New Delhi, IndiaPatiala House Courts ComplexGeneral informationStatusCompletedTypeDistrict courtsTown or cityNew DelhiCountryIndiaCoordinates28°36′56″N 77°14′05″E / 28.6155°N 77.2348°E / 28.6155; 77.2348Groundbreaking2004Construction started2004Completed2007Inaugurated2007Technical detailsFloor count5 Patiala House Courts Complex is one of the seven District Courts complexes located near India Gate in the National Capital Territory of Del...

 

American actor Britain DaltonDalton in 2019Born (2001-12-12) December 12, 2001 (age 21)Los Angeles, California, U.S.NationalityAmericanOccupationActorYears active2015–present Britain Dalton (born December 12, 2001) is an American actor known for his role as Lo’ak, the second son of Jake Sully and Neytiri, in the science fiction film Avatar: The Way of Water (2022). Career He started acting after a film student spotted him doing card tricks for a crowd on the street. The student ...

 

Japanese actor and singer You can help expand this article with text translated from the corresponding article in Japanese. (November 2018) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic...

Railway station in Miyako, Iwate Prefecture, Japan This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Sokei Station – news · newspapers · books · scholar · JSTOR (May 2020) (Learn how and when to remove this template message) Sokei Station磯鶏駅Sokei Station in September 2007General informationLocationSokei-...

 

الأحداث الواردة في هذه المقالة هي أحداث جارية وقد تكون عرضة لتغيرات سريعة وكبيرة. فضلًا، حدِّث المحتوى ليشمل أحدث المعلومات الموثوق بها المعروفة عن موضوع المقالة. هجمات الحوثيين على إسرائيل خلال عملية طوفان الأقصى جزء من الحرب الفلسطينية الإسرائيلية 2023  خريطة لهجما...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!