Preguntas etiquetadas con time-complexity

Complejidad temporal de problemas de decisión o relaciones entre clases de complejidad limitada en el tiempo. (Utilice la etiqueta [análisis de algoritmos] para el tiempo que requieren determinados algoritmos).

59
Una pila, dos colas

antecedentes Hace varios años, cuando era estudiante universitario, nos dieron una tarea de análisis amortizado. No pude resolver uno de los problemas. Lo había pedido en teoría teórica , pero no se obtuvieron resultados satisfactorios. Recuerdo que el curso TA insistió en algo que no pudo probar,...

22
¿Agregar números enteros representados por su factorización es tan difícil como factorizar? Solicitud de referencia

Estoy buscando una referencia para el siguiente resultado: Agregar dos enteros en la representación factorizada es tan difícil como factorizar dos enteros en la representación binaria habitual. (Estoy bastante seguro de que está ahí afuera porque esto es algo que me había preguntado en algún...

19
¿Por qué funcionan las bases de datos relacionales, dada la complejidad exponencial teórica de la búsqueda de respuestas (en el tamaño de la consulta)?

Parece que se sabe que para encontrar una respuesta a una consulta sobre una base de datos relacional , se necesita tiempo , y no se puede eliminar el exponente.QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Como puede ser muy grande, nos preguntamos por qué las bases de datos funcionan en la...

18
¿Es posible probar si un número computable es racional o entero?

¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...