¿Cuáles son las áreas / problemas de investigación actuales en informática teórica?

Principales problemas no resueltos en informática teórica:

• P = NP?
• La existencia de funciones unidireccionales
• ¿Es el isomorfismo gráfico en P?
• ¿Se puede multiplicar n por n matrices en operaciones O (n ^ 2)?
• ¿Está factorizando en P?
• P = BPP?
• ¿Podemos calcular la FFT en mucho menos tiempo que O (n logn)?
• ¿Existe una lógica que capture PTIME?
• NP = coNP?
• BQP = P?
• Un algoritmo determinista de tiempo lineal para el problema del árbol de expansión mínimo.
• ¿Existe un teorema de PCP cuántico?
• …

P = NP es probablemente el más famoso, aunque casi nadie cree que los problemas no polinómicos se puedan resolver en tiempo polinómico (es decir: P! = NP) y la solución muy probablemente no tenga aplicaciones prácticas.

El cifrado es otro tema muy candente, ya que es altamente matemático y teórico, pero sigue siendo un tema con aplicaciones muy prácticas.

Habría un debate en curso sobre lo que constituye la Ciencia de la Computación Teórica, excepto que los científicos están demasiado ocupados haciendo cosas reales como para perder el tiempo persiguiendo ratones. Otras respuestas han señalado lo que generalmente se entiende en Ciencias de la Computación Teórica (TCS): teoría de la complejidad, teoría de la computabilidad, teoría algorítmica, pero hay otros campos de la Ciencia de la Computación que son de naturaleza teórica pero no se consideran TCS, y son muy actuales.

1. Procesamiento de imágenes. ¿Cómo tomo cinco fotos hechas por personas aleatorias de Google Street View y hago un modelo de construcción en 3D con ellas? ¿Cómo tomo UNA foto de un objeto y lo convierto en un modelo 3D? ¿Cómo agrego un objeto CGI a una película y obtengo automáticamente la iluminación adecuada? etcétera etcétera.
2. Verificación generalizada formal. ¿Cómo construyo una CPU que no necesita una lista de erratas de 200 páginas, con errores como “si tres instrucciones de carga se ejecutan directamente una detrás de la otra, la tercera obtiene un resultado corrupto”? ¿Cómo construyo autos que siempre frenan cuando presiono los frenos? ¿Cómo construyo drones militares que no aterrizan en Irán? ¿Cómo construyo tanques que no dejen de disparar porque el enemigo lo hackeó? Y por no quiero decir ” no “, como 1 = 2 nivel de ” no “, no “0.1% de probabilidad” nivel de ” no “.
3. Seguridad. ¿Cómo comparto el estado del videojuego entre varios clientes para que los jugadores puedan jugar, pero no puedan ver a los enemigos a menos que estén dentro del alcance (es decir, no más mapas)? ¿Cómo creo un protocolo telefónico para el presidente que nadie más que el objetivo pueda escuchar? ¿Cómo puedo saber que alguien irrumpió en mi casa y reemplazó mi CPU con una que tiene una puerta trasera? ¿Cómo puedo compartir mis resultados de verificación generalizados formales sin tener que compartir ningún detalle sobre mi hardware / software con la competencia?

Hay muchos más, así que no te ofendas si no mencioné el tuyo 🙂

Pero como puede ver, hay muchas nueces difíciles de romper en las ramas teóricas de la informática.

¿Cómo escribir un trabajo de investigación sobre informática