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

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

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

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

Задача відноситься до класу 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 0-7167-1045-5.
  • п
  • о
  • р
Вважаються легкими
Припускаються складними
Вважаються складними
  • EXPTIME
  • NEXPTIME
  • EXPSPACE
  • 2-EXPTIME
  • PR
  • RE
  • Co-RE
  • RE-complete
  • Co-RE-complete
  • PH
Інше
Сигма Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.