É o suficiente para classificar polinomialmente muitas seqüências 0-1 para uma rede de classificação?

O princípio 0-1 diz que, se uma rede de classificação funciona para todas as seqüências 0-1, funciona para qualquer conjunto de números. Existe um tal que se uma rede classifica cada sequência 0-1 de S, ela classifica cada sequência 0-1 e o tamanho de S é polinomial em n ?$S\subset \{0,1\}^n$$S$$n$

Por exemplo, se consiste em todas as seqüências em que existem no máximo 2 execuções (intervalos) de 1, existe uma rede de classificação N e uma sequência que não é ordenada por N se todos os membros de S são ordenados por N?$S$$2$$S$

Resposta: Como pode ser visto na resposta e nos comentários, a resposta é que, para cada string não classificada, existe uma rede de classificação que classifica todas as outras string. Uma prova simples para isso é o seguinte. Deixe a corda ser tal que é i = 0 para sempre i < k e s k = 1 . Como s não é classificado, após a classificação, s k deve ser 0 . Compare k com cada i para o qual s i$s=s_1\ldots s_n$$s_i=0$$i<k$$s_k=1$$s$$s_k$$0$$k$$i$ . Em seguida, comparar cada par ( i , j ) de tal forma que i ≠ k e j ≠ k muitas vezes. Isso deixa a string inteira classificada, exceto possivelmente para s k , que não é classificada para s , e para certas outras strings que possuem mais 1 's que s . Agora compare s k para i = n downto 1 exceto para o lugar onde s k deve ir no s . Isso vai classificar tudo, menos s .$s_i=1$$(i,j)$$i\ne k$$j\ne k$$s_k$$s$$1$$s$$s_k$$i=n$$1$$s_k$$s$$s$

Atualização: Gostaria de saber o que acontece se restringirmos a profundidade da rede a .$O(\log n)$

Parece que não. Ian parberry faz referência a um artigo por Chung e Ravikumar, onde eles supostamente dar uma construção recursiva de uma rede de triagem que classifica cada bitstring mas um, e ainda deduzir que o problema de verificação de uma rede de triagem é - N P completa. Não consigo encontrar o documento original imediatamente, mas certamente corresponde à (minha) intuição.$co$$NP$

Editar para adicionar: na verdade, é muito fácil encontrar uma rede que perca exatamente uma string. A sequência a ser perdida será . Agora você só quer um circuito que classifique os últimos n - 1 bits e depois classifique os primeiros n - 1 bits. Este circuito irá classificar qualquer coisa com pelo menos dois 1 s, irá, obviamente, tipo todo-zero, corda, e irá classificar qualquer cadeia que começa com 0 .$(1,0,\ldots,0)$$n-1$$n-1$$1$$0$