4.5: Discusión

Última actualización
Guardar como PDF

Page ID: 118480

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Carlos, Dave y Yolanda quedaron fascinados por la discusión sobre la complejidad. Zori estaba menos entusiasta pero incluso ella sentía que la cuestión de qué problemas podrían resolverse rápidamente tenía implicaciones prácticas. Incluso podría predecir que la gente podría obtener un buen ingreso resolviendo problemas más rápido y con mayor precisión que su competencia.

Bob remarcó: “No estoy seguro de entender de lo que se habla aquí. No veo por qué no puede darse el caso de que se puedan resolver todos los problemas. A lo mejor simplemente no sabemos cómo hacerlo”. Xing dijo: “Cualquier problema finito puede ser resuelto. Siempre hay una manera de enumerar todas las posibilidades, compararlas una por una y tomar la mejor como respuesta”. Alice se unió: “Bueno, un problema puede llevar mucho tiempo solo porque es grande. Por ejemplo, supongamos que se le dan dos DVD's, cada uno completamente lleno con los datos para un entero grande. ¿Cómo es posible que los vas a multiplicar juntos, incluso con una computadora grande y un software elegante”. Carlos ofreció entonces: “Pero creo que hay problemas realmente duros que cualquier algoritmo tardará mucho en resolver y no sólo porque el tamaño de entrada es grande. En este punto, no sé cómo formular tal problema pero sospecho que existen”.