Оочень сложная задача по математике

если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время) , то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память) ? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?
Это д/з помогите кто-нибудь.
7 года назад от Олеся Коршунова

1 ответ

0 голосов
Увы, одна из центральных открытых проблем теории алгоритмов уже боле трёх десятилетий. Правда, определение проблемы оттуда и переписывалось. И да, слова "открытая проблема" означает, что решения нет. Увы. "Как и другие известные нерешённые математические проблемы, попытки решения этой задачи привлекают значительные усилия; регулярно публикуются (не в научной литературе) ошибочные доказательства равенства или неравенства классов P и NP, обычно непрофессионалами".
7 года назад от Регина

Связанные вопросы

1 ответ
Только мне кажется что мы родились в самое скучное время? Нам всем не повезло
1 год назад от ольга кузина
1 ответ
Порода собак или коров, и порода в угольной промышленности, почему такое сходство слов, есть ли разница или что общего ?
1 год назад от DwainFaison
2 ответа
А ведь даже иностранец хорошо знающий русский язык не сможет понять эту русскую речевую конструкцию? Со словом того
2 года назад от Андрей Наумов