Вообще
thesz — 10.05.2025
https://theory.stanford.edu/~trevisan/cs254-14/lecture03.pdfЧитаю такое и это натурально схоластика. Функция от n-битов входов в один бит выхода всегда имеет размер 2n, это доказывается построением не упрощённой BDD, фактически.
То есть, размер схемы экспоненциален не потому, что мы не можем построить схему меньшего размера, а потому, что мы всегда строим схему экспоненциального размера.
Найти результат нижней границы схемы или ожидаемый размер схемы для случайной таблицы истинности с использованием оптимизации не представляется возможным. Никто, похоже, этим не занимался.
|
|
</> |
Резиновая плитка от Altra Tyres: характеристики, плюсы и сферы применения 
