Карпов 21 НП-комплетан проблем

У теорији комплексности, Карпов 21 НП-комплетан проблем је скуп рачунских проблема који су НП-комплетни. У свом раду 1972. "Редуцибилитy Амонг Цомбинаториал Проблемс",^[1] Ричард Карп искористио је Стивен Кукову теорему из 1971. да је САТ проблем НП-комплетан^[2] (такодје звана Кук-Левинова теорема) да покаже да постоји полиномијално време смањивања сваког од 21 комбинаторна и графовска рачунска проблема, показујући тиме да су сви НП-комплетни. Ово је била једна од првих демонстрација од много рачунских проблема који се дешавају у информатици који су комплексни. Ова демонстрација буди интересовање за проучавање НП-комплетности и П=НП проблем.

Проблеми

Карпов 21 проблем, многи са својим оригиналним именима, су показани доле.

САТ проблем: проблем задовољивости коњуктивне нормалне форме
- 0-1 интегер программинг
- Цлиqуе
  - Сет пацкинг
  - Вертеx цовер
- Сатисфиабилитy wитх ат мост 3 литералс пер цлаусе
  - Цхроматиц нумбер (такође зван и Грапх Цолоринг Проблем)
    - Цлиqуе цовер
    - Еxацт цовер
      - Хиттинг сет
      - Стеинер трее
      - 3-дименсионал матцхинг
      - Кнапсацк
        Јоб сеqуенцинг
        
        Партитион
        Маx цут

Како је време пролазило је откривено да су многи проблеми могу ефикасно решавати, ако их ограничимо на посебне случајеве. Међутим, Давид Зуцкерман је показао 1996. да је сваки од ових 21 проблема има ограничену оптимизовану верзију која је немогуће приближити сталном фактору осим П = НП,показујући да је Карпов приступ смањењу генерализује на одређену врсту апроксимације смањења.^[3] Имајте на уму, међутим, да они могу да се разликују од стандардне верзије оптимизације проблема који могу имати алгоритми апроксимација.

Види још

Лист оф НП-цомплете проблемс

Референце

^ Карп, Рицхард M. (1972). „Редуцибилитy Амонг Цомбинаториал Проблемс” (ПДФ). Ур.: Р. Е. Миллер анд Ј. W. Тхатцхер (едиторс). Цомплеxитy оф Цомпутер Цомпутатионс. Неw Yорк: Пленум. стр. 85—103. Архивирано из оригинала (ПДФ) 29. 06. 2011. г. Приступљено 04. 06. 2013.
^ Степхен Цоок (1971). „Тхе Цомплеxитy оф Тхеорем Провинг Процедурес”. Процеедингс оф тхе тхирд аннуал АЦМ сyмпосиум он Тхеорy оф цомпутинг. стр. 151—158.
^ Зуцкерман, Давид (1996). „Он Унаппроxимабле Версионс оф НП-Цомплете Проблемс”. СИАМ Јоурнал он Цомпутинг. 25 (6): 1293—1304. дои:10.1137/С0097539794266407.

Литература

Карп, Рицхард M. (1972). „Редуцибилитy Амонг Цомбинаториал Проблемс” (ПДФ). Ур.: Р. Е. Миллер анд Ј. W. Тхатцхер (едиторс). Цомплеxитy оф Цомпутер Цомпутатионс. Неw Yорк: Пленум. стр. 85—103. Архивирано из оригинала (ПДФ) 29. 06. 2011. г. Приступљено 04. 06. 2013.
Степхен Цоок (1971). „Тхе Цомплеxитy оф Тхеорем Провинг Процедурес”. Процеедингс оф тхе тхирд аннуал АЦМ сyмпосиум он Тхеорy оф цомпутинг. стр. 151—158.

[1] Карп, Рицхард M. (1972). „Редуцибилитy Амонг Цомбинаториал Проблемс” (ПДФ). Ур.: Р. Е. Миллер анд Ј. W. Тхатцхер (едиторс). Цомплеxитy оф Цомпутер Цомпутатионс. Неw Yорк: Пленум. стр. 85—103. Архивирано из оригинала (ПДФ) 29. 06. 2011. г. Приступљено 04. 06. 2013.

[2] Степхен Цоок (1971). „Тхе Цомплеxитy оф Тхеорем Провинг Процедурес”. Процеедингс оф тхе тхирд аннуал АЦМ сyмпосиум он Тхеорy оф цомпутинг. стр. 151—158.

[3] Зуцкерман, Давид (1996). „Он Унаппроxимабле Версионс оф НП-Цомплете Проблемс”. СИАМ Јоурнал он Цомпутинг. 25 (6): 1293—1304. дои:10.1137/С0097539794266407.

[1]

[2]

[3]