Изменения
Нет описания правки
# Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
# Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
# Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкциядизъюнкция, используя $O(2^n)$ ребер.
# Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
= ЭТО НЕ КОНЕЦ, ЭТО ЕЩЕ ТОЛЬКО НАЧАЛО =
