Линейный алгоритм есть почти для любой задачи

Пятница, 24 Июля 2020 г. 18:38 + в цитатник

scrum0fscrums:

Цитата AVA12 @ 24.07.20, 14:06

Где утка?

Утка в том, что может и ошибка закралась. Что-то уж больно неправдоподобно. Тысячу раз уже и теорему Ферма доказывали и то, что P=NP и то, что P/=NP. И всё с ошибками как позже выяснялось.

Добавлено 24.07.20, 15:40

Цитата AVA12 @ 24.07.20, 13:06

If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size"

Это у них лемма. Далее доказывается линейность. Надо от начала до конца статью читать. Две статьи.

https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835115