Hasil berlawanan untuk sarjana

Saya mencari contoh hasil yang bertentangan dengan intuisi orang untuk pembicaraan khalayak umum. Hasil yang jika ditanyakan dari non-pakar "apa yang dikatakan intuisi Anda kepada Anda?", Hampir semua akan salah. Pernyataan hasil harus mudah dijelaskan kepada sarjana dalam cs / matematika. Saya terutama mencari hasil dalam ilmu komputer.

Apa hasil yang paling berlawanan / tidak terduga (dari kepentingan umum) di daerah Anda?

Untuk khalayak umum, Anda harus tetap berpegang pada hal-hal yang dapat mereka lihat . Segera setelah Anda mulai berteori mereka akan memulai ponsel mereka.

Berikut adalah beberapa ide yang dapat dikerjakan untuk melengkapi contoh:

1. Ada permukaan yang hanya memiliki satu sisi .
2. Kurva dapat mengisi seluruh kotak .
3. Ada kurva lebar konstan selain lingkaran.
4. Dimungkinkan untuk mewarnai pesawat dengan tiga warna sedemikian rupa sehingga setiap titik perbatasan adalah tri-perbatasan .

Jika Anda dapat mengandalkan sedikit pengetahuan matematika, Anda dapat melakukan lebih banyak:

1. Ada bilangan ganjil sebanyak jumlah alami.
2. Ada fungsi yang berkelanjutan dan tidak dapat dibedakan di mana-mana .
3. Ada fungsi yang terputus-putus di semua bilangan rasional dan dapat dibedakan di semua bilangan irasional.$f : \mathbb{R} \to \mathbb{R}$
4. The Banach-Tarski "paradoks" .

Untuk programmer Anda dapat mencoba:

1. The mustahil functionals : ada program yang membutuhkan predikat p : stream → bool, di mana streamadalah datatype urutan biner yang tak terbatas, dan kembali truejika dan hanya jika p αadalah trueuntuk semua aliran α(yang uncountably banyak), dan falsesebaliknya.

2. Dimungkinkan untuk bermain poker melalui telepon dengan cara tepercaya yang mencegah kecurangan.

3. Sekelompok orang dapat menghitung gaji rata-rata mereka tanpa ada yang mengetahui gaji orang lain.

4. Ada program yang membangun pohon biner $T$ dengan properti berikut:

   • pohon tidak terbatas$T$
   • tidak ada program yang melacak jalur tak terbatas di $T$

Satu ide adalah sesuatu yang sederhana dari algoritma streaming . Mungkin kandidat terbaik adalah algoritma mayoritas. Katakanlah Anda melihat aliran angka , satu demi satu, dan Anda tahu satu angka terjadi lebih dari separuh waktu, tetapi Anda tidak tahu yang mana. Bagaimana Anda dapat menemukan nomor mayoritas jika Anda hanya dapat mengingat dua angka sekaligus ? Jawabannya adalah algoritma Misra-Gries.$s_1, \ldots, s_n$

Pada setiap langkah Anda menyimpan angka dari arus dan penghitung frekuensi f . Pada awalnya Anda mengatur x ke angka pertama aliran dan menginisialisasi frekuensi f ke 1. Lalu setiap kali Anda melihat nomor baru s i , Anda memeriksa apakah x = s i . Jika x = s i , naikkan f ke f + 1 , jika tidak turun f ke f - 1 . Jika f = 0 , atur x ke s $x$$f$$x$$f$$s_i$$x = s_i$$x=s_i$$f$$f+1$$f$$f-1$$f=0$$x$$s_i$dan kembali ke 1 . Setelah elemen terakhir dari aliran, jika ada elemen mayoritas, itu akan sama dengan x .$f$$1$$x$

Gagasan lain adalah permainan terkenal untuk menggambarkan nol bukti pengetahuan . Saya pikir itu karena Oded Goldreich dan mirip dengan bukti nol pengetahuan untuk isomorfisme grafik.

Untuk membuat jawabannya mandiri, berikut ini permainannya. Misalkan Anda ingin meyakinkan teman buta warna Anda bahwa Anda dapat membedakan warna merah dari hijau. Teman Anda memiliki dua tumpukan kartu, dan dia tahu satu tumpukan berwarna hijau dan yang lainnya berwarna merah. Dia melakukan hal berikut tanpa Anda melihatnya: dengan probabilitas 1/2 dia menarik satu kartu dari setiap deck, dengan probabilitas 1/4 dia menarik dua kartu dari dek kiri, dan dengan probabilitas 1/4 dia menarik dua kartu dari dek kanan. . Kemudian dia menunjukkan kepada Anda kartu-kartu itu dan menanyakan apakah warnanya sama. Jika Anda tidak buta warna, tentu saja Anda dapat menjawab dengan benar setiap waktu. Jika Anda buta warna, Anda akan gagal dengan probabilitas 1/2. Jadi sekarang jika permainan dimainkan 10 kali, kemungkinan Anda bisa menang setiap kali menjadi buta warna sangat rendah.

Kicker adalah bahwa jika teman Anda tahu dua tumpukan kartu adalah dua warna yang berbeda, tetapi tidak tahu yang mana yang merah dan yang hijau, dia masih tidak akan tahu di akhir ini! Jadi dalam ringkasan:

1. Ada tempat untuk keacakan dalam bukti.
2. Anda dapat meyakinkan seseorang bahwa Anda tahu sesuatu tanpa memberi mereka informasi tentang hal itu.

Volume bola satuan dimensi pertama kali tumbuh seiring n tumbuh ( 2 , π , 4 π / 3 , … ) tetapi mulai menurun untuk n = 6 dan akhirnya konvergen ke 0 sebagai n → ∞ .$n$$n$$2,\pi,4\pi/3,\dots$$n=6$$0$$n\to\infty$

Hasil kontra intuitif dari teori kompleksitas adalah teorema PCP:

Secara informal, nyatakan bahwa untuk setiap masalah A , ada mesin Turing acak yang efisien yang dapat memverifikasi kebenaran bukti (bukti keanggotaan dalam A ) menggunakan nomor logaritmik bit acak dan hanya membaca jumlah bit konstan dari bukti. Konstanta dapat dikurangi menjadi 3 bit. Oleh karena itu, verifier acak hanya perlu membaca tiga bit dari bukti yang dinyatakan.$NP$$A$$A$

One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the students think they must first necessarily sort the array (in $O(n~lg ~n)$ time).

building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20^th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be systematized (somewhat in the form of what we now recognize as algorithmic) & somewhat via the concept of "finitism" (which has rough parallels to the idea of an algorithm as a finite sequence of steps). he proposed famous open problems along these lines. his (and others) intuition turned out to be wrong in a sort of spectacular way. the counterproof is Godels theorem and Turings Halting problem. both were initially extremely abstract concepts/ results and long, highly technical papers/ arguments only understandable to leading mathematicians of the time, but now are refined to simpler conceptual structures and taught to undergraduates. these were not initially seen as two aspects/face of the same phenomenon but now they are.

also it took close to ~¾ of a century to prove that integer Diophantine equations are undecidable, Hilberts 10th problem. this is counterintuitive in the sense that it was always known that number theory was extremely difficult but the concept that some specific/ identifiable problems in it may actually be "impossible to resolve" was nearly shocking at the time to some. undecidability continues to be a deep challenge in math/ TCS even as we have decades of exponential increases in hardware due to Moores law and yet massive supercomputers that are in a sense still "powerless against it". some aspects of the surprise of undecidability can be found in the book Mathematics, Loss of Certainty by Klein.

It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the population size).

Related to this is the birthday paradox of course.

Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models.

For example the rule 110 is efficiently (weakly) universal:

Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules:

we have a "working computer"! :-)

For the definition of "weakly" and "efficient", and for other examples of simple universal Turing machines look at: Turlough Neary, Damien Woods; The complexity of small universal Turing machines: a survey.

Another puzzling example is the Turing completeness of the FRACTRAN "programming language":

• the "program" is a list of fractions: $(p_1/q_1, p_2/q_2,..., p_n/q_n)$;
• given an input $n$ find the first $q_i$ that divides $n$ and replace $n \leftarrow n \cdot \frac{p_i}{q_i}$;
• repeat the previous step until no $q_i$ divides $n$.

With a suitable encoding of the input $n$, FRACTRAN can simulate any Turing machine.

You can also use other models, like cyclic tag systems, ant-automata, ....
The not-so-intuitive idea is that "computation" is hidden almost everywhere ... Wolfram wrote 1192 pages filled with figures and text to better express that idea in his A New Kind of Science (yes... yes... despite some critical reviews I finally bought a hard-copy of it :-)

A few good candidates off the top of my head:

• Every NFA has an equivalent DFA

• There exists a finite field of size $p$ or $p^i$ where $i \in \mathbb{N}$ and $i > 0$.

• Public key cryptography

  • Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs

  • RSA encrpytion

• Reed-Solomon codes

• Countability

  • $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{N} \times \mathbb{N}| = |\mathbb{Q}|$

  • The set of elements in the language $\{0,1\}^*$ is countable, but $\mathbb{R}$ is uncountable (Cantor's diagonalization)

  • Cantor's Theorem: $|S| < |\mathcal{P}(S)|$

• On a more philosophical level, it astonished me that Turing machines accurately define computation