English translation is not available yet. Showing Russian content.
NP-hard
NP-hard
Определение
Класс вычислительной сложности задач, для которых не известно алгоритма с полиномиальным временем решения, и которые как минимум так же сложны, как NP-полные задачи. Упоминается при анализе сложности механизмов аукционов (VCG).