Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

NP складна задача англ NP hard задача не менш складна ніж NP повна Задача Π є NP складною якщо існує NP повна задача Π1

NP-складна задача

NP-складна задача

NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π.

image
Співвідношення між класами P, NP, NP-Complete та NP-Hard у випадку вірності та хибності гіпотези P≠NP

Неформальний опис

Задача відноситься до класу 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 .
image Це незавершена стаття з математики.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, 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

Дата публікації:
Топ