NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWhMMkV3TDFCZmJuQmZibkF0WTI5dGNHeGxkR1ZmYm5BdGFHRnlaQzV6ZG1jdk16QXdjSGd0VUY5dWNGOXVjQzFqYjIxd2JHVjBaVjl1Y0Mxb1lYSmtMbk4yWnk1d2JtYz0ucG5n.png)
Неформальний опис
Задача відноситься до класу NP-hard, якщо вона є NP-повною або невідомий недетермінований алгоритм, що розв'язує її за поліноміальний час, тобто взагалі не належить класу NP. У випадку вірності гіпотези P≠NP, для розв'язання NP-складної задачі не існує поліноміального алгоритму.
Джерела
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN .
![]() | Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
NP skladna zadacha angl NP hard zadacha ne mensh skladna nizh NP povna Zadacha P ye NP skladnoyu yaksho isnuye NP povna zadacha P1 sho zvoditsya do P Spivvidnoshennya mizh klasami P NP NP Complete ta NP Hard u vipadku virnosti ta hibnosti gipotezi P NPNeformalnij opisZadacha vidnositsya do klasu NP hard yaksho vona ye NP povnoyu abo nevidomij nedeterminovanij algoritm sho rozv yazuye yiyi za polinomialnij chas tobto vzagali ne nalezhit klasu NP U vipadku virnosti gipotezi P NP dlya rozv yazannya NP skladnoyi zadachi ne isnuye polinomialnogo algoritmu DzherelaMichael R Garey and David S Johnson 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 0 7167 1045 5 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi