Я хочу знать, есть ли разница между NP-трудными проблемами и сложными вычислительными проблемами или эти два термина используются для одного и того же? Я попытался найти решение, но не могу получить разумный ответ. Кто-нибудь может помочь?Является ли Computationally-hard таким же, как NP-hard?
0
A
ответ
0
С учетом текущих знаний (до тех пор, пока на вопрос P = NP не ответил): Все проблемы с NP-трудностью сложны в вычислительной области. Но не все сложные вычислительные проблемы NP-hard (проблемы в P, с высокими показателями в полиноме, например).
Обратите внимание, что «NP-hard» - это четко определенный класс проблем в информатике. «С вычислительной точки зрения», с другой стороны, нет, насколько я знаю.