¿Hay problemas que se vuelven más fáciles a medida que aumentan de tamaño?

62

Esta puede ser una pregunta ridícula, pero ¿es posible tener un problema que en realidad se vuelve más fácil a medida que las entradas crecen en tamaño? Dudo que algún problema práctico sea así, pero tal vez podamos inventar un problema degenerado que tenga esta propiedad. Por ejemplo, tal vez comienza a "resolverse a sí mismo" a medida que crece, o se comporta de otra manera extraña.

algorithms asymptotics dsaxton
fuente

77

Un problema real con esta propiedad que viene a la mente es el descifrado de hash de contraseña sin sal cuando se formula como "dado n hashes, crackear al menos un hash". Dado que la velocidad de craqueo se escalaría linealmente con n, el tiempo de ejecución sería proporcional a 1 / n, excepto que en realidad no podemos asignar un tiempo definitivo ya que el craqueo es estocástico y no tiene un límite superior constante en el tiempo.

amon

1

@amon El tiempo de ejecución no escala como . ¡Toma tiempo solo leer los hashes que le han dado como entrada!

1 / n

$1/n$

n

$n$

n

$n$

David Richerby

3

¿Quieres decir más fácil en términos absolutos o relativos? ¿Qué medidas de costo permiten? ¿Requiere un costo estrictamente decreciente o no es suficiente (desde algún punto en adelante) suficiente?

Raphael

2

@DavidRicherby En este ejemplo, es legítimo ignorar el costo de leer la entrada siempre que no haga ninguna declaración sobre el costo absoluto. En cambio, la velocidad aumenta linealmente con la entrada. Por lo tanto, n • T (1)> T (n) incluso cuando se considera el costo de leer la entrada. Es decir, para este problema, es más fácil resolver una entrada grande de una vez en lugar de dividir la entrada, aunque el problema es divisible. No estoy diciendo que T (n)> T (n + 1) para todo n.

amon

44

Para todos los que quieran publicar otra respuesta del formulario, "Algún problema en el que la entrada es una pregunta más un montón de pistas sobre la respuesta": Esto no funciona. Las entradas más difíciles de longitud son aquellas en las que usa todos los bits para hacer la pregunta y no dar pistas. El hecho de que sea fácil lidiar con preguntas cortas con muchas sugerencias no significa que el peor tiempo de ejecución sea bueno.

n

$n$

n

$n$

David Richerby

39

No, no es posible: al menos, no en un sentido asintótico, donde se requiere que el problema se vuelva cada vez más fácil, para siempre, como . $n \to \infty$

Deje que sea el mejor tiempo de ejecución posible para resolver dicho problema, donde es el tamaño de la entrada. Tenga en cuenta que el tiempo de ejecución es un recuento del número de instrucciones ejecutadas por el algoritmo, por lo que debe ser un número entero no negativo. En otras palabras, para todo . Ahora, si consideramos una función , vemos que no existe tal función que disminuya estrictamente monotónicamente. (Sea lo que sea , tiene que ser finito, digamos ; pero luego, dado que está disminuyendo estrictamente monotónicamente, y $T(n)$ $n$ $T(n) \in \mathbb{N}$ $n$ $T: \mathbb{N} \to \mathbb{N}$ $T(0)$ $T(0)=c$ $T$ $T(c) \le 0$ $T(c+1) \le -1$ , lo cual es imposible.) Por razones similares, no existe una función que disminuya estrictamente asintóticamente: de manera similar, podemos demostrar que no existe una función de tiempo de ejecución donde exista tal que para todos , está disminuyendo estrictamente monotónicamente (cualquier función de este tipo tendría que volverse eventualmente negativa). $T(n)$ $n_0$ $n \ge n_0$ $T(n)$

Por lo tanto, tal problema no puede existir, por la sencilla razón de que los tiempos de ejecución deben ser enteros no negativos.

Tenga en cuenta que esta respuesta solo cubre algoritmos deterministas (es decir, el peor tiempo de ejecución). No descarta la posibilidad de algoritmos aleatorios cuyo tiempo de ejecución esperado disminuya estrictamente monotónicamente, para siempre. No sé si es posible que exista dicho algoritmo. Agradezco a Beni Cherniavsky-Paskin por esta observación .

DW
fuente

99

Esta es una buena prueba, pero no estoy de acuerdo con la premisa. En lugar de pedir un tiempo de ejecución estrictamente monotónicamente decreciente, la pregunta podría requerir más razonablemente una función donde exista a a, b con a <b para que T (a)> T (b), es decir, su disminución no estrictamente monotónica. Entonces, por supuesto, es posible encontrar funciones enteras adecuadas. ¿Pero por qué enteros? Tenía la impresión de que el tiempo de ejecución denotaba un tiempo, no un recuento de instrucciones (excepto, por supuesto, para las máquinas de Turing), y que la expresión T podía usar operaciones no enteras como log () o exponentes no enteros.

amon

2

@amon "el tiempo de ejecución indica un tiempo, no un recuento de instrucciones" Absolutamente no. El tiempo de ejecución es siempre un recuento de instrucciones. Cualquier otra cosa sería imposible de razonar, ya que dependería de muchos detalles de implementación.

David Richerby

3

Tan vaga como es la pregunta, no veo cómo excluye una función de costo de, digamos, . Ahora, pero para "pequeño" , por lo que el problema "se hace más fácil", en términos relativos. (Los costos absolutos crecen asintóticamente, por supuesto).

T (n) = n^{2} \cdot (1 + ϵ)^{- n} + n

$T(n) = n^2 \cdot (1+\epsilon)^{-n} + n$

T (n) \sim n

$T(n) \sim n$

T (n) \approx n^{2}

$T(n) \approx n^2$

n

$n$

Raphael

2

@Raphael, no es un problema cada vez más fácil: aumenta a medida que se hace más grande, por lo que el problema se vuelve más difícil a medida se hace más grande, una vez que es suficientemente grande. Dije en la primera oración de mi respuesta que ningún problema puede ser cada vez más fácil para siempre. Por supuesto, un problema puede ser más fácil por un tiempo ( puede estar disminuyendo para , por ejemplo), pero no puede seguir siendo más fácil para siempre.

T (n) \sim n

$T(n) \sim n$

T (n)

$T(n)$

n

$n$

n

$n$

n

$n$

T (n)

$T(n)$

n \leq c

$n \le c$

DW

1

Incluso con tiempos enteros, para un algoritmo aleatorio , el tiempo esperado (o cualquier otra medida de la distribución) puede ser fraccional y gradualmente podría acercarse a alguna constante desde arriba. [Esto no significa que tales problemas realmente existan, solo que el argumento "no existe tal función existe" es insuficiente.]

T

$T$

Beni Cherniavsky-Paskin

25

Aunque no es exactamente una respuesta a su pregunta, el algoritmo de búsqueda de cadenas de Boyer-Moore se acerca. Como Robert Moore dice en su página web sobre el algoritmo,

Nuestro algoritmo tiene la propiedad peculiar de que, en términos generales, cuanto más largo es el patrón, más rápido se vuelve el algoritmo.

En otras palabras, en general, el algoritmo busca una instancia de una cadena objetivo en una cadena fuente y una cadena fuente fija, cuanto más larga sea la cadena objetivo, más rápido se ejecutará el algoritmo.

Rick Decker
fuente

10

Podría decirse que el patrón no es el tamaño del problema, sino la longitud de la cadena que se busca. Como en el comentario anterior de David Richerby , argumentaría que la longitud del patrón es más una pista sobre cómo resolver el problema (sobre cómo buscar la cadena) que el problema en sí (ver si un patrón coincide con una cadena de una longitud particular .)

Kevin - Restablece a Mónica el

44

@Kevin La declaración sugiere que buscar un patrón de longitud en un texto de longitud es más rápido que buscar un patrón de longitud . Al observar tales entradas de relación fija (es decir, pares de cadenas), creo que Rick ha dado una respuesta adecuada a la pregunta (si no en el sentido clásico y asintótico).

\sqrt{n}

$\sqrt{n}$

n

$n$

\log n

$\log n$

Raphael

10

Claramente, desde un punto de vista matemático puro, puramente algoritmo CS, esto es imposible. Pero, de hecho, hay varios ejemplos del mundo real de cuándo ampliar su proyecto lo hace más fácil, muchos de los cuales no son intuitivos para los usuarios finales.

Instrucciones : cuanto más largas sean tus instrucciones, a veces pueden ser más fáciles. Por ejemplo, si quiero que Google Maps me dé instrucciones para ir hacia el oeste 3000 millas, podría conducir a la costa oeste y recibir instrucciones de manejo a través del país. Pero si quisiera ir 6000 millas al oeste, terminaría con instrucciones significativamente más simples: subirme a un avión desde Nueva York a Hokkaido. Darme una ruta a campo traviesa que incorpore tráfico, carreteras, clima, etc. es bastante difícil algorítmicamente, pero decirme que suba a un avión y busque vuelos en una base de datos es relativamente más simple. Gráfico ASCII de dificultad vs distancia:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Representación : digamos que quiero una representación de una cara y una representación de 1000 caras; esto es para un anuncio publicitario, por lo que ambas imágenes finales deben tener 10000 px por 5000 px. Renderizar una cara de manera realista sería difícil: a la resolución de varios miles de píxeles, debe usar máquinas realmente potentes, pero para la multitud de 1000 caras, cada cara solo necesita tener diez píxeles de ancho, ¡y puede clonarse fácilmente! Probablemente podría renderizar 1000 caras en mi computadora portátil, pero renderizar una cara realista de 10000 px de ancho requeriría mucho tiempo y máquinas potentes. Gráfico ASCII de dificultad frente a objetos renderizados, que muestra cómo la dificultad de representar n objetos en una imagen de un tamaño establecido disminuye rápidamente pero luego regresa lentamente:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects

Control de hardware : muchas cosas con hardware se vuelven mucho más fáciles. "Mover motor X 1 grado" es difícil y / o imposible, y tiene que lidiar con todo tipo de cosas con las que no tendría que lidiar para "mover motor X 322 grados".

Tareas de corta duración: supongamos que desea que el elemento X esté encendido (muy poco tiempo) cada segundo. Al aumentar la cantidad de tiempo que ejecuta X, necesitará software y hardware menos complejos.

Owen Versteeg
fuente

En su ejemplo de "instrucciones", indique exactamente cuál es el problema computacional y cuál es la instancia. No está nada claro para mí que su ejemplo de 6k millas sea una instancia más grande o simplemente un ejemplo de una parte fácil de algo (por ejemplo, si le doy un gráfico grande conectado a un gráfico más un vértice aislado, pedir en general rutas más cortas es "difícil", pero pedir un camino más corto desde el vértice aislado a cualquier lugar es trivial). Nuevamente, para su ejemplo de representación, ¿cuál es el problema computacional real? ¿Cuál es la instancia contra la cual estás midiendo la complejidad?

David Richerby

El ejemplo de representación no parece ser instancias del mismo problema: el primero es representar una sola imagen; la segunda representa muchas imágenes pequeñas y luego pega varias copias de esas imágenes en alguna área.

David Richerby

Creo que wrt para viajar los parámetros sería el nombre de las 2 ciudades y n sería el número de caracteres para codificarlas.

emory

3

Hay casos. Son los casos en los que el criterio de éxito es una función de los datos, en lugar de tratar de encontrar una respuesta única. Por ejemplo, los procesos estadísticos cuyos resultados se expresan con intervalos de confianza pueden volverse más fáciles.

Un caso particular en el que estoy pensando son los problemas que tienen una transición de comportamientos discretos a comportamientos continuos, como los flujos de fluidos. Resolver el pequeño problema dentro de un cierto grado de error puede implicar modelar todas las interacciones discretas, lo que puede requerir una supercomputadora. Los comportamientos continuos a menudo permiten simplificaciones sin producir resultados fuera de un límite de error relacionado.

Cort Ammon
fuente

2

La pregunta es interesante y ÚTIL, porque nuestra filosofía en informática es resolver problemas cuanto más leamos, más difícil será. Pero, de hecho, la MAYORÍA de los problemas que se presentan de la manera típica (difícil) se pueden representar fácilmente de la manera "fácil"; aun sabiendo la respuesta de DW (lo cual es incorrecto considerando que fácil no significa más rápido, significa "menos lento"; así que no tienes que encontrar tiempos negativos, tienes que encontrar el tiempo asintótico).

El truco para encontrar uno es poner la parte de la solución como pistas como una entrada, y considerar la entrada del problema como un parámetro constante.

Ejemplo: ¿Cuál es la forma más larga en automóvil entre Londres y París para evitar visitar dos veces una ciudad francesa y una británica y no visitar otro país? Ten en cuenta que debes ir a Birmingham antes que Ashford, Orleans antes que Versalles, La Rochelle antes que Limoge, etc.

Está claro que este problema con las entradas largas será más fácil que con las cortas.

Ejemplo de uso: imagine un juego administrado por la máquina, y la IA de la computadora tiene que determinar si tiene que explorar más en el juego para encontrar más pistas o si es el momento de deducir cuál es la mejor decisión para asumir .

Juan Manuel Dato
fuente

2

Tu ejemplo no funciona. Las instancias que son grandes porque tienen tantas pistas que las pistas determinan que un orden lineal de los vértices del gráfico son realmente fáciles. Sin embargo, las instancias que son grandes porque dan una gráfica grande casi sin pistas son tan difíciles como el problema del camino de Hamilton. Por lo tanto, el tiempo de ejecución en el peor de los casos de cualquier algoritmo que resuelva este problema será al menos tan malo como el tiempo de ejecución en el peor de los casos del mejor algoritmo para la ruta hamiltoniana, que no parece ser "súper fácil".

David Richerby

@David, su respuesta es completamente incorrecta: 1. La entrada no es un gráfico: el gráfico grande es un PARÁMETRO. Entonces, el problema hamiltoniano se convierte en una constante (muy grande, pero constante). 2. La entrada es la solución del problema, entonces: si es mayor, está ofreciendo una explosión combinatoria de pistas. Una entrada de una pista da una ayuda, dos pistas el doble, tres pistas estarán cerca de 4 veces ..., porque está eliminando posibles soluciones. Entonces, esto no era un hamiltoniano, esta es una solución de un gráfico específico y el problema es QUÉ hacer con partes de las soluciones.

Juan Manuel Dato

Creo que su argumento es interesante ya que las instancias más grandes son "más fáciles" en algún sentido, pero creo que la respuesta a la pregunta original es en última instancia "no". Como el gráfico es finito, solo hay muchas sugerencias posibles. Por lo tanto, cada instancia se puede resolver en tiempo constante (por ejemplo, usando una tabla de búsqueda). Aunque las instancias más grandes son (intuitivamente) más fáciles en la visión de la informática (asintótica), todas las instancias son igualmente difíciles (solucionables en tiempo constante).

Tom van der Zanden

@ Tom, estoy de acuerdo en que su consideración sobre la complejidad será constante, pero el problema es cómo estamos aceptando las nuevas sugerencias: si con nuestra filosofía de calcular la entrada larga no es mejor que una entrada corta, entonces tenemos que cambiar nuestra filosofía - porque eso es un hecho: las entradas largas implican problemas más fáciles. Así que no podemos trabajar de esa manera ... recomendaría mi libro, pero no tengo reputación ...

Juan Manuel Dato

n \log n

$n\log n$

1

Considere un programa que toma como entrada lo que sabe sobre una contraseña y luego intenta descifrarla. Creo que esto hace lo que quieres. Por ejemplo:

Sin entrada-> Fuerza bruta crack sobre todos los símbolos y una palabra de cualquier longitud
Longitud de la contraseña -> Fuerza bruta todos los símbolos en una palabra de esa longitud
Símbolos contenidos -> Reduce la lista de símbolos para verificar
...
Símbolos contenidos que incluyen múltiples ocurrencias y longitud -> Solo calcular permutaciones
Todos los símbolos en el orden correcto -> básicamente se resolvieron solos

Debo agregar que esto es un truco, ya que el problema planteado de esta manera es inverso al tamaño de entrada. Puede omitir una capa de abstracción y decir que el tamaño de entrada es grande para ninguna entrada (verifique todos los símbolos y longitudes de palabras) y pequeño si ingresa la contraseña correcta al principio.

Así que todo se reduce a cuánta abstracción permites.

RunOrVeith
fuente

2

b

$b$

0

De hecho, tengo un problema que se reduce a medida que aumentan los datos. Una de mis aplicaciones registra los atributos de un producto en particular, digamos queso. Los atributos son, por ejemplo, CheeseType, Brand, Country, Area, MilkType, etc. Cada mes más o menos, recibo una lista de los nuevos quesos que llegaron al mercado durante ese tiempo, junto con sus atributos. Ahora, estos atributos están escritos a mano por un grupo de humanos. Algunos hacen errores tipográficos, o simplemente no conocen el valor de todos los atributos.

Cuando realiza una búsqueda en mi base de datos, trato de predecir a partir de las estadísticas a qué sabe el queso, según estos atributos. Lo que sucede es que para cada atributo, termino con un rango de valores; algunos son válidos algunos no son válidos. Eliminar o corregir estos no válidos solo es posible si tengo suficientes datos. Se trata de marcar la diferencia entre los valores reales y el ruido, sin eliminar valores raros pero válidos.

Como puede imaginar, con un volumen bajo, el ruido es demasiado importante para arreglar las cosas correctamente. Si tiene 5 instancias de Cheddar, 1 de Brie, 1 de Bri y 1 de Chedar, ¿cómo puedo saber cuál es correcto y cuál es un error tipográfico? Con más volumen, los errores tipográficos tienden a mantenerse muy bajos, pero los valores raros obtienen algunos incrementos cruciales, lo que los hace escapar del ruido (respaldado por la experiencia). En este caso, podría imaginar 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar, por ejemplo.

Entonces, sí, algunos problemas se resuelven por sí solos cuando tienes suficientes datos.

Chris
fuente

1

Esto falla por la razón habitual. Una entrada grande podría ser una en la que las personas le cuenten sobre muchos tipos diferentes de queso, en lugar de una en la que le cuenten sobre algunos tipos de queso, pero algunos de ellos lo escriben mal. Además, no está claro que se suponga que "más fácil" debe interpretarse como "permitir una mayor confianza en el resultado".

David Richerby

Este es un problema de la vida real (ya lo he tenido dos veces), que no se puede resolver con poca cantidad de datos. Puede, e incluso se hace más fácil distinguir, buenos valores de los incorrectos, a medida que el volumen aumenta. Tiene el mérito de responder la pregunta "¿Hay problemas que se vuelven más fáciles a medida que aumentan de tamaño?" No importa cuántos tipos de quesos surjan, eventualmente, con suficiente volumen, tendrán más "hits" que los errores tipográficos. Esto es cs .stackexchange, no matemáticas, por lo que los problemas son diferentes, y resolverlos a veces se trata simplemente de tener una mayor confianza en los resultados.

Chris

¿No es esto también una especie de premisa del programa de televisión Numbers ? O al menos algunos episodios: sé que recuerdo específicamente una escena en la que el chico de matemáticas comenta que el algoritmo que está usando para resolver el problema en cuestión se vuelve más efectivo con un conjunto de datos más grande.

Dan Henderson el

2

"Se vuelve más efectivo"! = "Se vuelve más fácil".

David Richerby

-1

Considere el problema NP-completo 3-SAT. Si sigue aumentando el problema al proporcionar entradas de la forma x_i = verdadero / falso, termina convirtiendo las disyunciones individuales en cláusulas de dos variables, creando así un problema 2-SAT que es decididamente P, o simplemente termina obteniendo Una respuesta verdadera / falsa.

Para el caso de que haya redundancia en las entradas x_i = verdadero / falso (la misma entrada se proporcionó muchas veces o entradas contradictorias), puede clasificar fácilmente las entradas e ignorar los valores redundantes o informar un error si los valores se contradicen.

En cualquier caso, creo que esto representa un problema 'realista' que se vuelve más fácil de resolver a medida que aumenta el número de entradas. El aspecto 'más fácil' es convertir un problema NP-completo en un problema P. Todavía puede jugar el sistema al proporcionar entradas ridículas de tal manera que solo la clasificación tomaría más tiempo que el bruto forzando el problema.

Ahora, un escenario realmente genial sería si estamos dispuestos a aceptar T (0) (utilizando la notación de DW en la respuesta anterior) puede ser infinito. Por ejemplo, T (0) podría ser equivalente a resolver el problema de detención de Turing. Si pudiéramos idear un problema tal que agregar más entradas lo convierta en un problema solucionable, habríamos encontrado oro. Tenga en cuenta que no es suficiente convertirlo en un problema solucionable asintóticamente, porque eso es tan malo como la fuerza bruta del problema.

v vv cvvcv
fuente

1

Estas entradas particulares se vuelven más fáciles. Sin embargo, cuando considera todas las entradas posibles, 3SAT en general se vuelve significativamente más difícil a medida que agrega más cláusulas: las entradas duras son las que no tienen estas cláusulas "indirectas". Si no permite entradas generales, debe indicar exactamente qué entradas está permitiendo.

David Richerby

En primer lugar: estamos de acuerdo en que agregar más entradas puede aumentar el tiempo de ejecución. Yo digo esencialmente lo mismo de arriba. En segundo lugar, digo claramente que estamos tomando un 3-SAT existente y agregando solo entradas de la forma x_i = verdadero / falso. Creo que esto es lo suficientemente claro y no necesito hacer más aclaraciones. Creo que te estás tomando la molestia de formar la interpretación más mal interpretada de lo que he escrito. Por favor no te preocupes.

v vv cvvcv

1

No en serio. ¿Qué problema computacional estás resolviendo? Un problema computacional es decidir la membresía de un conjunto de cadenas (digamos un conjunto de fórmulas para evitar molestias sobre la codificación). ¿Cuál es el conjunto de fórmulas para las cuales afirma que decidir si una fórmula larga está en el conjunto es más fácil que decidir que una fórmula corta está en el conjunto? Tan pronto como intente precisar esto, estoy bastante seguro de que su reclamo se desmoronará.

David Richerby

¿Puede por favor hacer explícito su comprensión de 'mi reclamo'? Tan pronto como intente precisar esto, estoy bastante seguro de que dejará de desperdiciar el ancho de banda de Internet.

v vv cvvcv

Soy un informático, no un lector de mente. Hacer su reclamo con precisión es su trabajo, no el mío.

David Richerby

-1

La pregunta es: "¿es posible tener un problema que en realidad se hace más fácil a medida que las entradas crecen en tamaño?" ¿Qué pasa si las entradas son recursos para ser utilizados por el algoritmo para trabajar en un trabajo? Es de conocimiento común que cuantos más recursos, mejor. A continuación se muestra un ejemplo, en el que cuanto más empleados haya, mejor.

$n$
$t$ $p$

$n$

3) Salida:
la salida es la ruta entre las tareas que deben tomar los empleados. Cada ruta está asociada con la cantidad de empleados que la toman. Por ejemplo:

$n1$
$n2$
$n3$
$n4$
$n5$

4) Posible solución:
una posible solución es calcular primero la ruta más corta a los nodos más cercanos desde A. Esta será una ruta directa. Luego, recursivamente calcule la ruta hacia adelante para cada tarea visitada. El resultado es un árbol. Por ejemplo:

          UNA
      antes de Cristo
    Delaware

$n$ $n1$ $n2$ $n2 \neq 0$

$n=\infty$ $n = 1$

$n$

yemelitc
fuente

66

Gracias por compartir tus pensamientos. Normalmente, en informática, se entiende que un algoritmo acepta una secuencia de bits como su entrada y genera otra secuencia de bits. Con esa comprensión estándar, no veo cómo esta respuesta puede tener sentido. Si tiene en mente una noción diferente de algoritmo, creo que sería útil que editara la pregunta para describir lo que quiere decir con algoritmo (ya que parece que no está usando el término de una manera que corresponde al uso estándar de término, según lo entiendo).

DW

La entrada puede ser simplemente un número (el número de recursos). Esto afectará la cantidad de cálculo adicional que tendrá que pasar el algoritmo. Editaré la respuesta para proporcionar un ejemplo más concreto.

yemelitc

Gracias por tu edición, eso lo hace mucho más claro. Ahora veo que no estás confundiendo el costo de calcular la solución con el costo de ejecutarla como pensé originalmente. Pero ahora estamos en la situación habitual. Primero, se necesita al menos un tiempo lineal para leer la entrada. En segundo lugar, las instancias difíciles no son aquellas en las que le das un árbol pequeño y un millón de personas, sino donde le das un árbol grande y relativamente pocas personas. (Por ejemplo, si me permite un millón de bits, elegiré un árbol con aproximadamente mil vértices y le daré cinco personas, no un árbol con cinco vértices y mil personas.)

David Richerby

Estoy de acuerdo. ¡Parece que todos terminamos siendo bastante críticos al respecto, a diferencia de lo que nos tentaba la pregunta original! Pero espero que entiendan mi idea de "entrada como recurso": no importa cuán grande sea el trabajo, cuantas más personas, mejor. Aún así, en un sentido asintótico, definitivamente tienes razón, debería culpar a los enteros no negativos.

yemelitc

¿Hay problemas que se vuelven más fáciles a medida que aumentan de tamaño?

Respuestas: