Принцип 0-1 говорит, что если сеть сортировки работает для всех последовательностей 0-1, то она работает для любого набора чисел. Существует ли такое, что если сеть сортирует каждую последовательность 0-1 из S, то она сортирует каждую последовательность 0-1, а размер S является полиномиальным по n ?
Например, если состоит из всех последовательностей, в которых не более 2 серий (интервалов) из 1, то существует ли сортирующая сеть N и последовательность, которая не упорядочена по N, если все члены S упорядочены по N?
Ответ. Как видно из ответа и комментариев к нему, ответ заключается в том, что для каждой несортированной строки существует сеть сортировки, которая сортирует все остальные строки. Простое доказательство этого заключается в следующем. Пусть строка такова, что s i = 0 для всех i < k и s k = 1 . Поскольку s не отсортировано, после сортировки s k должно быть 0 . Сравните k с каждым i, для которого s i = . Затем сравните каждую пару ( i , j ) так , чтобы i ≠ k и j ≠ k много раз. Это оставляет всю строку отсортированной, за исключением, возможно, s k , который неотсортировандля s , и для некоторых других строк, которые имеют больше 1 , чем s . Теперь сравните s k для i = n до 1, за исключением места, где s k должно идти в s . Это будет сортировать все, кроме с .
Обновление: интересно, что произойдет, если мы ограничим глубину сети .
источник
Ответы:
Кажется нет. Ян Парберри ссылается на статью Чанга и Равикумара, где они предположительно дают рекурсивное построение сортировочной сети, которая сортирует каждую цепочку битов, кроме одной, и далее выводят, что проблема проверки сортировочной сети - N P завершена. Я не могу сразу найти оригинал, но, конечно, он соответствует (моей) интуиции.co NP
Изменить, чтобы добавить: На самом деле очень легко найти такую сеть, которая пропускает ровно одну строку. Пропущенная строка будет . Теперь вам просто нужна схема, которая сортирует последние n - 1 бит, а затем сортирует первые n - 1 бит. Эта схема будет сортировать что-либо по крайней мере с двумя 1 с, очевидно, будет сортировать строку со всеми нулями и будет сортировать любую строку, начинающуюся с 0 .(1,0,…,0) n−1 n−1 1 0
источник