Problém dvou loupežníků

Problém dvou loupežníků je v matematické informatice NP-úplný problém, jak rozdělit kořist (oceněné věci) mezi dva loupežníky tak, aby lup byl rozdělen rovným dílem (součet hodnot věcí v jedné skupině byl roven součtu hodnot věcí v druhé skupině).

Mějme zadáno ${\displaystyle N}$ čísel. Otázka zní: Lze zadaná čísla rozdělit do dvou skupin tak, aby součet čísel v obou skupinách byl stejný (tj. aby se dva loupežníci mohli spravedlivě rozdělit o kořist ${\displaystyle N}$ oceněných věcí)?

Pokud je čísel málo, řešení lze nalézt celkem snadno — pomocí prozkoumání všech možných rozdělení čísel do dvou skupin. Počet možných rozdělení do dvou skupin však roste exponenciálně, a pokud bychom si vzali např. ${\displaystyle N=50}$, pak stavový prostor v rozumném čase neprojdeme ani na výkonném počítači.

• NP-úplnost
• Stavový prostor

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.