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

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

1 ответ



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

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

3 ответов
а кто правильно использует: от кутюр? гурман? брутал? а кто-нибудь действительно понимает по-русски? )
12 года назад от дмитрий гаврилов
1 ответ
Для чего на место пожара могут вызывать электриков?
1 год назад от Влад Боровской
2 ответов
Как называется прокручивание в голове произошедшего спора и придумывание лучшего ответа или аргумента для спора?
9 месяцев назад от сергей дроздов