Я уверен, что кто-то думал об этом раньше или сразу же отклонил это, но почему теория дихотомии Шефера наряду с теоремой Махани о разреженных множествах не подразумевает P = NP?
Вот мои рассуждения: создайте язык который равен SAT, пересекаемому бесконечным разрешимым разреженным множеством. Тогда L также должен быть разреженным. Поскольку L не является тривиальным, аффинным, 2-сат или рогово-сат, по теореме Шефера он должен быть NP-полным. Но тогда мы имеем разреженный NP-полный набор, так что по теореме Махани, P = NP.
Куда я здесь не так? Я подозреваю, что я неправильно понимаю / неправильно применяю теорему Шефера, но не понимаю почему.
Ответы:
источник