Powszechne fałszywe przekonania w informatyce teoretycznej

62

EDYCJA PRZY 10/12/08:

Spróbuję zmodyfikować pytanie, aby zainteresować większą liczbą osób dzieleniem się opiniami. POTRZEBUJEMY twoich datków!

Ten post jest inspirowany jednym z MO: Przykłady powszechnych fałszywych przekonań w matematyce . Wielkie listy czasami generują ogromną liczbę odpowiedzi, których jakości trudno jest kontrolować, ale po sukcesie powiązanego postu na MO jestem przekonany, że pomocne byłoby wymienienie wielu powszechnych fałszywych przekonań w TCS.

Mimo to, ponieważ strona jest przeznaczona do odpowiadania na pytania na poziomie badań, przykłady, takie jak $\mathsf{NP}$ oznacza zakaz wielomianowym czasie nie powinno być na liście. Tymczasem chcemy kilku przykładów, które mogą nie być trudne, ale bez szczegółowego zastanowienia wygląda to również rozsądnie. Chcemy, aby przykłady miały charakter edukacyjny i zwykle pojawiają się podczas studiowania tego tematu po raz pierwszy.

Jakie są (nietrywialne) przykłady powszechnych fałszywych przekonań w teoretycznej informatyce, które wydają się ludziom studiującym w tej dziedzinie?

Dokładniej mówiąc, chcemy przykładów innych niż zaskakujące wyniki i sprzeczne z intuicją wyniki w TCS; tego rodzaju wyniki sprawiają, że ludzie trudno w to uwierzyć, ale są PRAWDĄ. W tym miejscu prosimy o zaskakujące przykłady, które ludzie mogą na pierwszy rzut oka sądzić, że to prawda, ale po głębszym zastanowieniu ujawnia się wada wewnętrzna.

Jako przykład poprawnych odpowiedzi na liście, ta pochodzi z dziedziny algorytmów i teorii grafów:

Dla wykresie -node , A -edge separatora jest podzbiorem krawędzi rozmiarze , gdzie węzły może być podział na dwie niesąsiadujące części, z których każda składa się z co najwyżej węzłów . Mamy następujący „lemat”: $n$ $G$ $k$ $S$ $k$ $G \setminus S$ $3n/4$

Drzewo ma 1-krawędziowy separator.

Dobrze?

big-list examples Hsien-Chih Chang 張顯之
źródło

Wpis został oznaczony jako prośba o CW.

Hsien-Chih Chang 之之

59

Jest to powszechne w przypadku geometrii obliczeniowej, ale endemiczne gdzie indziej: Algorytmy dla prawdziwej pamięci RAM można przenosić do całkowitej liczby pamięci RAM (w przypadku ograniczeń liczby całkowitej problemu) bez utraty wydajności. Kanonicznym przykładem jest twierdzenie: „Eliminacja Gaussa przebiega w czasie ”. W rzeczywistości nieostrożne porządki eliminacji mogą generować liczby całkowite o wykładniczo dużej liczbie bitów . $O(n^3)$

Co gorsza, ale wciąż niestety powszechne: Algorytmy dla prawdziwej pamięci RAM z funkcją floor można przenosić do całkowitej liczby pamięci RAM bez utraty wydajności. W rzeczywistości podłoga z prawdziwą pamięcią RAM + może rozwiązać każdy problem w PSPACE lub w #P w wielomianowej liczbie kroków .

Jeffε
źródło

5

Gaussowskie błędne przekonanie o eliminacji jest bardzo rozpowszechnione. Być może częścią problemu jest to, że często pracujemy na skończonych polach, a ponieważ nie ma tam problemu, zapominamy.

slimton,

„Po przeprowadzeniu całkowitej eliminacji Gaussa wiemy, jak znaleźć rozwiązanie”.

Albert Hendriks,

40

Właśnie dostałem kolejny mit, do którego przyczynia się odpowiedź @ XXYYXX na ten post :

Problem X oznacza -hard jeśli jest wielomianem czasu (lub logspace) zmniejszenie wszystkich problemy z X. $\mathsf{NP}$ $\mathsf{NP}$
Załóżmy hipotezę o wykładniczym czasie, 3-SAT nie ma sub wykładniczego algorytmu czasu. Ponadto, 3-SAT w . $\mathsf{NP}$
Więc nie ma -hard problemy X mają sub-wykładnicze algorytmów czasowych. W przeciwnym razie algorytm subwykładniczy dla X + redukcja czasu wielomianowego = algorytm subwykładniczy dla 3-SAT. $\mathsf{NP}$

Ale mamy algorytmy sub wykładnicze czasu dla niektórych problemów trudnych dla NP.

Hsien-Chih Chang 張顯之
źródło

Miałem to samo wrażenie.

Mohammad Al-Turkistany,

Co to mówi nam o hipotezie o wykładniczym czasie? A może brakuje mi wady w tym rozumowaniu?

Michaił Glushenkov,

2

W punkcie 3 jest błąd. Dokładnie tego źle zrozumiałem przez długi czas :)

Hsien-Chih Chang 之之

Nie jestem pewien, czy nie mogę znaleźć usterki. Czy to dlatego, że od

, redukcja niekoniecznie musi być wielomianowa, ale że może być wykładnicza w czasie, ponieważ oba problemy byłyby w WYGODZIE (z powodu ETH?)

P \neq N P

$P \neq NP$

Chazisop

43

Skrócenie czasu wielomianu może zmienić rozmiar wejściowy o wielkość wielomianową. Jeśli więc zredukujesz wystąpienie Q o rozmiarze n do wystąpienia P o rozmiarze n do kwadratu, algorytm 2 do pierwiastka n dla P daje tylko 2 do algorytmu n dla Q.

Russell Impagliazzo

29

Fałszywe przekonanie, które zostało spopularyzowane w tym roku i powiedziano wiele razy, gdy ktoś próbuje wyjaśnić cały problem , ponieważ jest wyjaśnione jako skuteczne: $P \neq NP$ $P$

„Jeśli , możemy skutecznie rozwiązać ogromną liczbę problemów. Jeśli nie, nie możemy” $P=NP$

Jeśli może być rozwiązany w , a następnie . Nie sądzę, żeby ktokolwiek nawet pomyślał o uruchomieniu tego algorytmu. $3SAT$ $O(n^{googolplex})$ $P=NP$

Jeśli , nadal możemy mieć algorytm dla działający w , który jest mniejszy niż dla . Większość ludzi byłaby bardzo szczęśliwa, gdyby mogła szybko rozwiązać dla 4 miliardów miast. $P \neq NP$ $TSP$ $n^{\log(\log n)}$ $n^{5}$ $n\leq2^{32}$ $TSP$

chazisop
źródło

5

Post na blogu autorstwa Liptona jest ładny: rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem

Hsien-Chih Chang 之之

6

„Dla każdego algorytmu czasu wielomianowego istnieje algorytm wykładniczy, który wolałbym uruchomić” - Alan Perlis, za pośrednictwem Lost Letter Gödela i P = NP .

Pål GD

24

To jest naprawdę fałszywe przekonanie w matematyce, ale często pojawia się w kontekstach TCS: jeśli zmienne losowe i są niezależne, to zależne od pozostają niezależne. (fałsz, nawet jeśli jest niezależny zarówno od jak i ). $X$ $Y$ $Z$ $Z$ $X$ $Y$

MCH
źródło

2

Czy masz ulubiony prosty przykład, który byś polecił, aby pomóc ludziom szybko rozpoznać, dlaczego jest to nieprawda?

DW

21

Powiedzmy, że

i

są niezależnymi i jednakowo losowymi bitami, a

(mod 2). Wówczas

jest niezależne od

i jest niezależne od

, ale uwarunkowane od

, wiedząc, że

ujawnia

i odwrotnie.

X

$X$

Y

$Y$

Z = X + Y

$Z = X+Y$

Z

$Z$

X

$X$

Y

$Y$

Z

$Z$

X

$X$

Y

$Y$

MCH

22

Przetwarzanie rozproszone = rozproszone obliczenia o wysokiej wydajności (klastry, siatki, chmury, seti @ home, ...).

Algorytmy rozproszone = algorytmy dla tych systemów.

Spoiler: Jeśli to nie brzmi jak „fałszywe przekonanie”, sugeruję, abyś rzucił okiem na konferencje, takie jak PODC i DISC, i zobaczysz, jaką pracę naprawdę wykonują ludzie, badając teoretyczne aspekty przetwarzania rozproszonego.

Typowe ustawienie problemu jest następujące: Mamy cykl z węzłami; węzły oznaczone są z unikalnymi identyfikatorami z zestawu ; węzły są deterministyczne i wymieniają między sobą wiadomości w sposób synchroniczny. Ile rund komunikacji synchronicznej (w funkcji ) jest potrzebnych do znalezienia maksymalnego niezależnego zestawu? Ile rund jest potrzebnych do znalezienia niezależnego zestawu z co najmniej węzłami? [Odpowiedź na oba te pytania to dokładnie $n$ $\{1,2,...,\text{poly}(n)\}$ $n$ $n/1000$ , odkryty w latach 1986–2008.] $\Theta(\log^* n)$

Oznacza to, że ludzie często badają problemy, które są całkowicie trywialne z punktu widzenia scentralizowanych algorytmów i mają bardzo niewiele wspólnego z jakimkolwiek rodzajem superkomputerów lub obliczeń o wysokiej wydajności. Chodzi oczywiście o to, aby nie przyspieszyć scentralizowanego obliczenia poprzez użycie większej liczby procesorów lub czegoś podobnego.

Celem jest zbudowanie teorii złożoności poprzez klasyfikację podstawowych problemów graficznych zgodnie z ich złożonością obliczeniową (np. Ile potrzebnych jest rund synchronicznych; ile bitów jest przesyłanych). Problemy takie jak niezależne zestawy w cyklach mogą wydawać się bezcelowe, ale pełnią rolę podobną do 3-SAT w scentralizowanym przetwarzaniu: bardzo przydatny punkt początkowy w redukcji. W przypadku konkretnych rzeczywistych aplikacji bardziej sensowne jest spojrzenie na urządzenia takie jak routery i przełączniki w sieciach komunikacyjnych, a nie na komputery w sieciach i klastrach.

To fałszywe przekonanie nie jest całkowicie nieszkodliwe. W rzeczywistości utrudnia to sprzedaż prac związanych z teorią algorytmów rozproszonych ogółowi odbiorców TCS. Otrzymałem zabawne raporty sędziów z konferencji TCS ...

rev Jukka Suomela
źródło

1

Jeśli chodzi o informatykę, nie powiedziałbym, że to nie jest fałszywe przekonanie, ale raczej przestarzałe. Inne niż procesory wielordzeniowe, rozproszone obliczenia na małą skalę były banalnym przypadkiem tego, który charakteryzował się wysoką wydajnością (z tego co wiem przynajmniej). Ponieważ rdzenie są „komputerami”, ale na tak małej odległości, bez sieci między nimi, pojawiają się nowe problemy. Zgadzam się jednak, że algorytmy rozproszone powinny być stosowane dla m> = 2 węzłów.

chazisop

Mówisz tylko, że ludzie mylą obliczenia równoległe z obliczeniami rozproszonymi?

Sasho Nikolov

Myślę, że twoje twierdzenie nie dotyczy teoretycznych informatyków, choć może dotyczyć pratictionersów bez teoretycznego zaplecza. Jak zauważył Sasho Nikolov, osoby pracujące w tej dziedzinie doskonale znają różnice między obliczeniami równoległymi i rozproszonymi. Problem pojawiający się w klastrach, siatkach, chmurach itp. Ściśle zależy od kontekstu. Na przykład nie zakładamy awarii podczas korzystania z klastra lub chmury, ale robimy to w przypadku siatek. I tak dalej.

Massimo Cafaro

Co więcej, dla tej społeczności naukowej algorytmy rozproszone są algorytmami dla problemów, takich jak te powszechnie spotykane w książkach Nancy Lynch, Hagit Attiya i Jennifer Welch oraz Gerarda Tel, aby wymienić tylko kilka. I jako takie, algorytmy te są zaprojektowane dla konkretnego teoretycznego modelu rozproszonego przetwarzania danych i analizowane zgodnie z wymaganiami pod kątem wykorzystywanych zasobów (złożoność czasu, złożoność komunikatu, złożoność bitów, liczba rund itp.).

Massimo Cafaro

@MassimoCafaro: Oczywiście ludzie pracujący w dziedzinie przetwarzania rozproszonego wiedzą, co to jest przetwarzanie rozproszone. Jednak z mojego doświadczenia wynika, że teoretycy informatyki w ogóle nie wiedzą, co to jest przetwarzanie rozproszone.

Jukka Suomela

20

$T(n) = 2T(n/2) + O(n \log n)$ $T(1) = 1$

$n=1$ $n$

$\begin{align} T(n) &= 2 \cdot T(n/2) + O(n \log n) \\ &= 2 \cdot O(n/2 \log n/2) + O(n \log n) \\ &= O(n \log n/2) + O(n \log n) \\ &= O(n \log n) \\ \end{align}$

QED (prawda?)

Hsien-Chih Chang 張顯之
źródło

16

f (x) = O (g (x))

$f(x) = O(g(x))$

f (x) \in O (g (x))

$f(x) \in O(g(x))$

Widziałem też naukowców zajmujących się informatyką teoretyczną, którzy również robią warianty tego błędu;)

Jeremy

12

$M$ $T(n)$ $M_o$ $O(T(n)\log T(n))$

$M_o$
$M_o$ $\Theta(T(n)\log T(n))$

(zobacz na przykład ten post rjlipton)

$EXP-TIME\neq NEXP-TIME$ $\Theta(T(n)\log T(n))$ $M_o$ $M_o$ $O(T(n)\log T(n))$ $T:\mathbb{N}\rightarrow\mathbb{N}$ $\Theta(T(n)\log T(n))$ $O(T(n)\log T(n))$ $EXP-TIME=NEXP-TIME$

Dowód tego twierdzenia jest bardzo podobny do dowodu w odpowiedzi na pytanie 1 tutaj , dlatego podamy tylko kluczowe pomysły.

$L\in NEXP-TIME$ $L\subseteq\{0,1\}^*$ $k\in\mathbb{N}$ $L$ $M$ $2^{n^k}$ $M$

f (n) = {\begin{cases} (8 n + 2)^{2} & if (first ⌊ \sqrt[k]{⌊ \log n ⌋ + 1} ⌋ bits of b i n (n)) \in L \\ 8 n + 1 & else \end{cases}

$f(n)=\left\{\begin{array}{ll} (8n+2)^2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\ 8n+1 & \mbox{else} \end{array} \right.$

f

$f$

$g(n)=\Theta(f(n)\log f(n))$ $g$

$L$

$x$ $n$ $x00\ldots 0$ $|x|^{k-1}$ $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$
$g(n)$ $g(n)$ $g(n)$ $x\in L$ $x\not\in L$ $n$ $g$

$L$ $L\in NEXP-TIME$ $EXP-TIME=NEXP-TIME$

David G.
źródło

11

Oto moje dwa centy:

$\mathsf{RL}$ $\mathsf{RP}$ $M$

$M$ $1/2$
$M$ $1$

Ponadto maszyna zawsze się zatrzymuje.

Czy definicja jest poprawna? (Nie)

Hsien-Chih Chang 張顯之
źródło

9

$f$ $g$ $1^n$ $f(n)$ $g(n)$ $f(n+1)=o(g(n))$

$NTIME(f(n))\subsetneq NTIME(g(n))$

$NTIME(g(n)) - NTIME(f(n))\neq\emptyset$ $f(n)\leq g(n)$ $NTIME(f(n))\subsetneq NTIME(g(n))$ $f,g$ $f(n+1)=o(g(n))$ $f(n)\leq g(n)$

$NTIME(f(n))\subseteq NTIME(g(n))$ $f,g$ $f(n+1)=o(g(n))$

f (n) = {\begin{cases} n + 1 & n odd \\ (n + 1)^{3} & else \end{cases}

$f(n)=\left\{\begin{array}{ll} n+1 & n \mbox{ odd}\\ (n+1)^3 & \mbox{else} \end{array} \right.$

g (n) = f (n + 1)^{2}

$g(n)=f(n+1)^2$

f

$f$

g

$g$

f (n + 1) = o (g (n))

$f(n+1)=o(g(n))$

L \in N T I M E ((n + 1)^{3}) - N T I M E ((n + 1)^{2})

$L\in NTIME((n+1)^3)-NTIME((n+1)^2)$

{0, 1}

$\{0,1\}$

L_{1} = {0 x_{1} 0 x_{2} \dots 0 x_{n}; x_{1} x_{2} \dots x_{n} \in L} .

$L_1=\{0x_10x_2\ldots 0x_n;\ \ x_1x_2\ldots x_n\in L\}.$

$L_1\in NTIME(f(n))$ $L_1\in NTIME(g(n))$ $L\in NTIME((n+1)^2)$ $L_1\in NTIME(f(n))-NTIME(g(n))$

David G.
źródło

9

$\mathsf{NP}$ $\mathsf{UP}$ $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{UP}}$ $\mathsf{NP} \subseteq \mathsf{R} \cdot \mathsf{UP}$ $\mathsf{NP}=\mathsf{UP}$ $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$

$\mathsf{UP}$ $L$ $x \in L$ $\mathsf{US}$ $\mathsf{US}$ $\mathsf{UP}$ $\mathsf{coNP} \subseteq \mathsf{US}$

Joshua Grochow
źródło

co oznacza „właściwość semantyczna, która we wszystkich przypadkach”?

T ....

1

@ 777: właściwość semantyczna oznacza: nie można zweryfikować bezpośrednio ze struktury (inaczej składni) samego algorytmu / TM. Fraza ma sens, jeśli przejdziesz obok przecinka, tj .: właściwość, która: „we wszystkich przypadkach jest co najwyżej jeden świadek”

Joshua Grochow

-2

$\mu$ $X$ $\{X=\mu\}$

użytkownik1596990
źródło

9

Jest to z pewnością wspólny fałszywe przekonanie wśród studentów teoretycznej informatyki, ale nie jest to tak powszechne wśród teoretycznych informatyki badaczy .

Jeffε

Powszechne fałszywe przekonania w informatyce teoretycznej

Odpowiedzi: