Czy wystarczy sortować wielomianowo wiele sekwencji 0-1 dla sieci sortującej?

Zasada 0-1 mówi, że jeśli sieć sortująca działa dla wszystkich sekwencji 0-1, to działa dla dowolnego zestawu liczb. Czy istnieje taki, że jeśli sieć sortuje każdą sekwencję 0-1 od S, to sortuje każdą sekwencję 0-1, a wielkość jest wielomianowa w ? $S\subset \{0,1\}^n$ $S$ $n$

Na przykład, jeśli $S$ składa się ze wszystkich sekwencji, w których występują co najwyżej przebiegi (przedziały) 1, to czy istnieje sieć sortująca N i sekwencja, która nie jest uporządkowana przez N, jeśli wszyscy członkowie są uporządkowani przez N? $2$ $S$

Odpowiedź: Jak widać z odpowiedzi i komentarzy do niej, odpowiedź jest taka, że dla każdego nieposortowanego ciągu istnieje sieć sortująca, która sortuje każdy inny ciąg. Prosty dowód na to jest następujący. Niech ciąg będzie taki, że na zawsze i . Ponieważ jest nieposortowane, po sortowaniu powinno wynosić . Porównaj z każdym dla którego $s=s_1\ldots s_n$ $s_i=0$ $i<k$ $s_k=1$ $s$ $s_k$ $0$ $k$ $i$ . Następnie porównaj każdą parę $s_i=1$ tak, że i wiele razy. Pozostawia to cały ciąg posortowane, z wyjątkiem być może dla , która jest dla nieposortowanego , a dla niektórych innych ciągów, które mają więcej „s niż . Teraz porównaj dla downto z wyjątkiem miejsca, w którym powinno iść w . To posortuje wszystko oprócz . $(i,j)$ $i\ne k$ $j\ne k$ $s_k$ $s$ $1$ $s$ $s_k$ $i=n$ $1$ $s_k$ $s$ $s$

Aktualizacja: Zastanawiam się, co się stanie, jeśli ograniczymy głębokość sieci do . $O(\log n)$

ds.algorithms sorting sorting-network domotorp
źródło

Wydaje się, że jest to możliwe, należy ograniczyć wielkość sieci sortowania być mniejszy niż rozmiar

. W przeciwnym razie, czy sieć nie mogłaby po prostu sprawdzić, czy dane wejściowe są jednym z elementów

i działać poprawnie, jeśli tak, w przeciwnym razie działać nieprawidłowo?

S

$S$

S

$S$

usul

@usul: Nie sądzę, żeby sieć sortująca mogła sprawdzić coś takiego. W każdym razie naturalną rzeczą jest praca z sieciami sortującymi, których rozmiar jest wielomianowy w

n

$n$

domotorp

Odpowiedzi:

Wydaje się, że nie. Ian Parberry odnosi się do pracy przez Chung Ravikumar, gdzie podobno daje rekurencyjnego budowę sieci sortowania sortuje każdy łańcuch bitów, lecz jeden, i dalej wywnioskować, że problem sprawdzania sortowania sieci jest - zakończona. Nie mogę od razu znaleźć oryginalnego papieru, ale z pewnością pasuje on do (mojej) intuicji. $co$ $NP$

Edytuj, aby dodać: W rzeczywistości bardzo łatwo jest znaleźć taką sieć, w której brakuje dokładnie jednego ciągu. Ciąg do pominięcia to . Teraz potrzebujesz obwodu, który sortuje ostatnie bity, a następnie sortuje pierwsze bity. Ten obwód posortuje wszystko z co najmniej dwoma s, oczywiście posortuje ciąg zerowy i posortuje dowolny ciąg zaczynający się od . $(1,0,\ldots,0)$ $n-1$ $n-1$ $1$ $0$

Andrew D. King
źródło

Czy przykładową sieć sortującą w odpowiedzi można uogólnić, tak aby dla dowolnego ciągu można było zbudować sieć sortującą, która źle sortuje ten ciąg? Pokazujesz, jak to zrobić dla jednego określonego ciągu, ale co z innymi ciągami?

Z pewnością możesz to zrobić dla dowolnego ciągu o masie

lub

, ale wątpię, czy można pominąć pojedynczy dowolny ciąg bitów.

1

$1$

n - 1

$n-1$

Andrew D. King

OK, więc nie widzę, jak twoja odpowiedź pokazuje, że odpowiedź brzmi „nie”. Konstrukcja w drugim akapicie twojej odpowiedzi nie oznacza negatywnej odpowiedzi na pierwotne pytanie, ponieważ jest tylko wielomianowo wiele ciągów o masie

lub

. Wydaje się, że cała praca w twojej odpowiedzi jest wykonywana przez odniesienie w pracy Iana Parberry, ale to zdanie w pracy Parberry jest raczej niejasne i bez przeczytania pracy Chunga i in. Nie widzę, jak możemy dojść do wniosku, że odpowiedź na pytanie brzmi „nie”.

1

$1$

n - 1

$n-1$

Bardziej utożsamianie: „ Silna niedeterministyczna redukcja Turinga - technika dowodzenia nietrwałości ” (Chung i Ravikumar) wymienia następujące elementy jako Lemma 2.1: biorąc pod uwagę dowolny nieposortowany ciąg

, istnieje sieć sortująca o wielomianowym rozmiarze, która poprawnie sortuje wszystkie ciągi oprócz

. Jako dowód odnosi się do „O rozmiarze zestawów testowych do sortowania i powiązanych problemów” (Chung i Ravikumar), ale nie mogę znaleźć kopii tego ostatniego artykułu. Oznaczałoby to, że odpowiedź na to pytanie brzmi „nie”.

x

$x$

x

$x$

Artykuł Chunga i Ravikumara

Kristoffer Arnsfelt Hansen