Np-тўликлик масаласи

Таърифдан шундай хулоса келиб чиқадики, агар NP-тўлиқ масаласи полиномиаль вақтда ҳал қиладиган алгоритм топилса, унда барча NP-тўлиқ масалалар P синфга жойлаштирилади, яъни улар полиномиаль вақтда ечилади.

NP-тўликлик масаласининг кучлилик томони

Агар масаланинг қисим масалалари мавжуд бўлса у кучли NP-тўлиқ масала дейилади, бунда: Масаланинг рақамли параметрлари мавжуд бўлмаса (яъни, бу масалада учрайдиган катталикларнинг максималь қиймати полином узунлиги билан юқоридан чегараланган).

Масаланинг рақамли параметрлари мавжуд бўлмаса (яъни, бу масалада учрайдиган катталикларнинг максималь қиймати полином узунлиги билан юқоридан чегараланган).

NP-тўликлик масала.

Бундай вазифалар синфи NPCS деб номланади. Aгар P ≠ NP гипотезаси тўғри бўлса, унда NPCS масаласи учун сохтаополиномиал алгоритм мавжуд эмас.

NP-тўликлик масалага мисоллар

• Буль формулалари бажарилиши масаласи
• "Доғлар" n × n ўлчамининг энг қисқа ечими
• Коммивояжёра масаласи
• Штейнер муаммоси
• Графани бўяш масаласи
• Соха (юза) қопламаси масаласи
• Тўпламни қоплаш масаласи
• Танлаш масаласи
• Тўпламнинг мустақиллиги масаласи
• Сапер (ўйин)
• Тетрис

Адабиётлар

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задач. М.: Мир, 1982.
• Томас Х. Кормен и др. Боб. 34 NP-полнота // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. — ISBN 0-07-013151-1.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.