Умные вопросы
Войти
Регистрация
Оочень сложная задача по математике
если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время) , то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память) ? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?
Это д/з помогите кто-нибудь.
6 года
назад
от
Олеся Коршунова
1 ответ
▲
▼
0
голосов
Увы, одна из центральных открытых проблем теории алгоритмов уже боле трёх десятилетий. Правда, определение проблемы оттуда и переписывалось. И да, слова "открытая проблема" означает, что решения нет. Увы. "Как и другие известные нерешённые математические проблемы, попытки решения этой задачи привлекают значительные усилия; регулярно публикуются (не в научной литературе) ошибочные доказательства равенства или неравенства классов P и NP, обычно непрофессионалами".
6 года
назад
от
Регина
Связанные вопросы
1
ответ
Все знакомы со Вторым началом термодинамики и энтропией, а как её можно понизить, если она всегда только повышается?
3 года
назад
от
Анна Миргородская
4
ответов
Как происходит стабилизация напряжения?
9 года
назад
от
Максут Измуханов
1
ответ
Почему электронные книги на электронных чернилах (черно белые) стоят по прежнему дорого?
7 года
назад
от
Ерш