0-1 принцип

Есть два способа проверить сеть из n компараторов на то, что она сортирующая. Первый, наивный способ - перебрать все перестановки из n элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует [math] O(n! \cdot Comp(n)) [/math] действий, где [math] Comp(n) [/math] - количество компараторов в сети из n элементов. Обычно это количество можно оценить как [math] n^2 \log n [/math](сеть Бэтчера), то есть получаем асимптотику [math] O(n! n^2 \log n) [/math], то есть при n, равном уже 10, проверить сеть очень проблематично. Второй способ основывается на предположении что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Докажем это.