Resultados contraintuitivos para estudiantes universitarios

14

Estoy buscando ejemplos de resultados que van en contra de la intuición de las personas para una audiencia general. Resultados que, si se les pregunta a los no expertos "¿qué te dice tu intuición?", Casi todos se equivocarían. La declaración de resultados debe ser fácilmente explicable a los estudiantes de pregrado en cs / matemáticas. Principalmente busco resultados en informática.

¿Cuáles son los resultados más contraintuitivos / inesperados (de interés general) en su área?

Anónimo
fuente
77
estrechamente relacionados: cstheory.stackexchange.com/q/276/4896 y cstheory.stackexchange.com/q/2802/4896
Sasho Nikolov
1
El segundo enlace de Sasho es un duplicado, ¿no?
Huck Bennett
Similar pero no igual. Estoy buscando resultados que sean interesantes y contrarios a la intuición para estudiantes universitarios generales de cs / matemáticas, no investigadores. Por ejemplo, IP = PSPACE no sería una buena respuesta.
Anónimo
44
Para tamaños de entrada suficientemente grandes, la primalidad siempre se puede decidir en menos tiempo que La forma más rápida conocida de tener una posibilidad no despreciable de factorizar un módulo RSA.

Respuestas:

25

Para una audiencia general, debe atenerse a las cosas que pueden ver . Tan pronto como comiences a teorizar, ellos encenderán sus teléfonos móviles.

Aquí hay algunas ideas que podrían elaborarse para completar ejemplos:

  1. Hay una superficie que tiene solo un lado .
  2. Una curva puede llenar un cuadrado entero .
  3. Hay curvas de ancho constante que no sean un círculo.
  4. Es posible colorear el plano con tres colores de tal manera que cada punto de borde sea un triple borde .

Si puede confiar en un poco de conocimiento matemático, puede hacer más:

  1. Hay tantos números impares como números naturales.
  2. Hay una función continua y en ninguna parte diferenciable .
  3. Hay una función que es discontinua en todos los números racionales y diferenciable en todos los números irracionales.F:RR
  4. La "paradoja" de Banach-Tarski .

Para programadores puedes probar:

  1. Los funcionales imposibles : hay un programa que toma un predicado p : stream → bool, donde streamestá el tipo de datos de secuencias binarias infinitas, y devuelve truesi y solo si p αes truepara todos los flujos α(eso es incontablemente muchos), y de lo falsecontrario.

  2. Es posible jugar al póker por teléfono de manera confiable, lo que evita las trampas.

  3. Un grupo de personas puede calcular su salario promedio sin que nadie descubra el salario de otra persona.

  4. Hay un programa que construye un árbol binario T con las siguientes propiedades:

    • el árbol es infinitoT
    • no hay ningún programa que rastree un camino infinito en T
Andrej Bauer
fuente
La paradoja de Banach-Tarski (y las paradojas relacionadas) tienen que ver con las nociones (y manipulaciones) del infinito, algo que incluso los matemáticos profesionales pueden equivocarse (o estar muy en desacuerdo) :)
Nikos M.
44
De acuerdo, pero es el tipo de teorema indignante que despierta el interés de las personas. Les da una sacudida y les hace dudar de sus propias intuiciones sobre el infinito.
Andrej Bauer
17

Una idea es algo simple de los algoritmos de transmisión . Probablemente el mejor candidato es el algoritmo mayoritario. Supongamos que ve una secuencia de números , uno tras otro, y sabe que un número aparece más de la mitad del tiempo, pero no sabe cuál. ¿Cómo puedes encontrar el número mayoritario si solo puedes recordar dos números a la vez ? La respuesta es el algoritmo Misra-Gries.s1,,sn

En cada paso de tiempo, almacena un número de la transmisión y un contador de frecuencia f . Al principio, establece x en el primer número de la secuencia e inicializa la frecuencia f en 1. Luego, cuando vea un nuevo número s i , verifique si x = s i . Si x = s i , aumente f a f + 1 , de lo contrario disminuya f a f - 1 . Si f = 0 , establezca x en s ixfxfsix=six=siff+1ff1f=0xsiy volver a 1 . Después del último elemento de la secuencia, si hubiera un elemento mayoritario, será igual a x .f1x

Otra idea es el conocido juego para ilustrar cero pruebas de conocimiento . Creo que se debe a Oded Goldreich y es similar a la prueba de conocimiento cero para el isomorfismo gráfico.

Para hacer que la respuesta sea autónoma, aquí está el juego. Suponga que quiere convencer a su amigo daltónico de que puede distinguir el rojo del verde. Tu amigo tiene dos barajas de cartas, y sabe que una pila es verde y la otra es roja. Hace lo siguiente sin que lo veas: con una probabilidad de 1/2 roba una carta de cada mazo, con una probabilidad de 1/4 roba dos cartas del mazo izquierdo y con una probabilidad de 1/4 roba dos cartas del mazo derecho . Luego te muestra las cartas y te pregunta si son del mismo color. Si no es daltónico, por supuesto, puede responder correctamente cada vez. Si es daltónico, fallará con probabilidad 1/2. Entonces, si el juego se juega 10 veces, la probabilidad de que puedas ganar cada vez que eres daltónico es extremadamente baja.

El truco es que si tu amigo sabía que las dos barajas de cartas son de dos colores diferentes, pero no sabía cuál es el rojo y el verde, ¡aún no sabrá al final de esto! Entonces en resumen:

  1. Hay lugar para la aleatoriedad en las pruebas.
  2. Puedes convencer a alguien de que sabes algo sin darle ninguna información al respecto.
Sasho Nikolov
fuente
3
Además de Misra-Gries, también creo que el muestreo de yacimientos es simple pero agradable.
Juho
1
@Juho estoy de acuerdo. Una pregunta de entrevista popular para arrancar :).
Sasho Nikolov
13

El volumen de una esfera unitaria de dimensión primero crece a medida que n crece ( 2 , π , 4 π / 3 , ... ) pero comienza a disminuir para n = 6 y finalmente converge a 0nortenorte2,π,4π/3,n=60 como .n

Denis
fuente
1
Y la razón de esto es la decisión arbitraria de considerar esferas de radio unitario, en oposición a otro parámetro de longitud. En particular, los volúmenes de esferas de diámetro 1 están disminuyendo desde el primer momento.
Emil Jeřábek apoya a Monica el
Hay muchos hechos divertidos y contraintuitivos relacionados con la geometría en altas dimensiones. Por ejemplo, tome el hipercubo de la unidad e inscriba una esfera que toque todos los lados. ¿A qué distancia está una esquina del hipercubo de la esfera? (Respuesta: diverge a medida que crece la dimensión. El radio de la esfera es 0.5 , pero la distancia del centro a la esquina del cubo es 0.5 0.5 .)0.5norte
usul
10

Un resultado contrario intuitivo de la teoría de la complejidad es el teorema de PCP:

Informalmente, establece que para cada problema A , hay una máquina Turing aleatoria eficiente que puede verificar la corrección de la prueba (prueba de pertenencia a A ) utilizando un número logarítmico de bits aleatorios y leyendo solo un número constante de bits de la prueba. La constante se puede reducir a 3 bits. Por lo tanto, el verificador aleatorio necesita leer solo tres bits de la prueba proclamada.NPAA

Mohammad Al-Turkistany
fuente
¿Cuál es la referencia para "puede reducirse a 3 bits"?
Ryan
2
Eso se conoce como el teorema de PCP de 3 bits (o 3 consultas) de Håstad, y requiere sacrificar la integridad perfecta
Joe Bebel
1
Aquí encontrará más información y la referencia al artículo de Håstad: people.csail.mit.edu/madhu/papers/1998/glst.pdf
Mohammad Al-Turkistany
66
@JoeBebel En realidad, hay verificadores de 3 bits con integridad perfecta. El verificador de Hastad es "lineal": toma muestras de tres bits y toma su XOR. Para tal verificador necesitas sacrificar la integridad perfecta. Por cierto, hay pruebas de PCP que leen solo dos bits (de nuevo necesariamente sin una integridad perfecta). Por ejemplo, vea mi respuesta aquí cstheory.stackexchange.com/a/20549/4896
Sasho Nikolov
9

inO(n)O(n lg n) time).

Massimo Cafaro
fuente
7

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 20th 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.

vzn
fuente
2
Turing's paper was not extremely abstract/technical. It's actually quite straightforward and accessible.
Jeffε
1
fine, maybe for you, now, but how many undergraduates do you know who can follow the entire paper? did you follow it as an undergraduate? why are the full actual contents not covered in undergrad classes? why has an entire book been written analyzing that single paper? what about parts that anticipate concepts not discovered until decades later such as curry-howard correspondence, high level programming languages, etc?
vzn
3
Still, "long, highly technical papers/ arguments only understandable to leading mathematicians of the time" is not accurate wrt Turing's paper, which is orders of magnitude more accessible than Godel's papers. This answer is full of non-sequitirs. I cannot see what finitism has to do with Hilbert's program (I am certain he would not have been a finitist). What Moore's law has to do with undecidability is also a puzzle to me. Would you really expect exponentially faster hardware would solve undecidable problems?
Sasho Nikolov
3
why are the full actual contents not covered in undergrad classes? — Not enough time.
Jeffε
1
Fair enough, I did not know about Hilbert's finitism. I was only familiar with modern and much stricter notions of finitism. It would be better if you wrote a good answer rather than refer people to chat, but I somehow doubt you'd follow this advice.
Sasho Nikolov
6

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.

Suresh Venkat
fuente
5

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:

ingrese la descripción de la imagen aquí

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: (p1/q1,p2/q2,...,pn/qn);
  • given an input n encuentra el primero qyo eso divide n y reemplazar nnortepagyoqyo;
  • repita el paso anterior hasta que no qyo divide norte.

Con una codificación adecuada de la entrada norte, FRACTRAN puede simular cualquier máquina de Turing.

También puede usar otros modelos, como sistemas de etiquetas cíclicas, autómatas, ...
La idea no tan intuitiva es que el "cálculo" está oculto en casi todas partes ... Wolfram escribió 1192 páginas llenas de figuras y texto para mejorar expresa esa idea en su Un nuevo tipo de ciencia (sí ... sí ... a pesar de algunas críticas críticas, finalmente compré una copia impresa de la misma :-)

Marzio De Biasi
fuente
3

Algunos buenos candidatos de la parte superior de mi cabeza:

  • Cada NFA tiene un DFA equivalente

  • Existe un campo finito de tamaño pag o pagyo dónde yonorte y yo>0 0.

  • Criptografía de clave pública

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

    • RSA encrpytion

  • Reed-Solomon codes

  • Countability

    • |N|=|Z|=|N×N|=|Q|

    • El conjunto de elementos en el lenguaje. {0 0,1} es contable, pero R es incontable (diagonalización de Cantor)

    • Teorema de Cantor: El |SEl |<El |PAG(S)El |

  • En un nivel más filosófico, me sorprendió que las máquinas de Turing definieran con precisión la computación

Bharadwaj Ramachandran
fuente