Supongamos que no conocemos el resultado de Joe B. Wells de 1994 de que tanto la tipificación como la verificación de tipo son indecidibles en el Sistema F (AKA ). En los cálculos Lambda con tipos de Barendregt (1992) encontré una prueba debido a Malecki 1989 de que la verificación de tipos implica...
Es bien sabido que la complejidad de la consulta cuántica de error acotado de la función es Θ ( √OR(x1,x2,…,xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n). Ahora la pregunta es ¿y si queremos que nuestro algoritmo cuántico tenga éxito para cada entrada con probabilidad1-εen lugar de la habitual2/3....
Intrigado por la interesante pregunta de Chris Pressey sobre funciones recursivas elementales , estaba explorando más y no pude encontrar una respuesta a esta pregunta en la web. Las funciones recursivas elementales corresponden muy bien a la jerarquía exponencial,
Aquí está el trasfondo de esta pregunta. Amigos y yo estábamos jugando un juego en el que todos necesitan darle un regalo a otra gente. Para determinar quién debe dar un regalo a quién, decidimos sortear. Pero el problema es que alguien podría terminar dándose regalos, lo cual no es divertido....
Lo siguiente me parece una definición natural y me pregunto si se ha estudiado en alguna parte Considere un conjunto de idiomas. Entonces se llama " -información verificable" cuando hay stX⊂2{0,1}∗X⊂2{0,1}∗\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}K⊂{0,1}ωK⊂{0,1}ωK \subset \lbrace 0, 1...
Me encontré con este problema de coincidencia para el que no puedo escribir un algoritmo de tiempo polinómico. Supongamos que sean gráficos ponderados completos con conjuntos de vértices P V y Q V , respectivamente, donde | P V | = | Q V | = n . Además, dejar que w P y w Q ser las funciones de...
es bien sabido que el cálculo μ modalμμ\mu es una de las lógicas temporales más expresivas para expresar las propiedades de los árboles / gráficos, y que CTL * es estrictamente menos expresivo que el cálculo .μμ\mu Aquí me gustaría pedir un ejemplo de fórmula de cálculo , tan simple como sea...
¿Cada lenguaje indecidible reconocible de Turing tiene un subconjunto NP-completo? La pregunta podría verse como una versión más fuerte del hecho de que cada lenguaje infinito reconocible de Turing tiene un subconjunto infinito
En el artículo de Adi Shamir [1] de 1979, muestra que la factorización se puede hacer en un número polinómico de pasos aritméticos . Este hecho fue reiterado, y por lo tanto me llamó la atención, en el reciente artículo de Borwein y Hobart [2] en el contexto de los programas de línea recta...
Estoy interesado en compiladores verificados formalizados en la teoría de tipo Martin-Löf, es decir, Coq / Agda. Por el momento he escrito un pequeño ejemplo de juguete. Con eso puedo demostrar que mis optimizaciones son correctas. Por ejemplo, las adiciones con cero pueden eliminarse, es decir,...
Sea la clase de lenguajes que se decida alternando máquinas de Turing que se detengan en el tiempo utilizando el espacio . Sea la clase de lenguajes que se decida alternando máquinas de Turing que dejen de usar las alternancias y el espacio .f ( n ) g ( n ) A A L T S P ( f ( n ) , g ( n ) ) f ( n )...
Estoy confundido. Quiero demostrar que el problema de ordenar una matriz por , es decir, las filas y columnas están en orden ascendente es . Continúo asumiendo que se puede hacer más rápido que e intento violar el límite inferior Para las comparaciones necesarias para ordenar m elementos. Tengo...
¿Existe una familia conocida de acciones grupales con un elemento designado en el conjunto sobre el que se está actuando, donde se sabe cómo eficientemente \: muestra (esencialmente uniforme) de los grupos, calcula las operaciones inversas, calcula las operaciones del grupo y calcula las...
Considere un problema en el que se le proporciona una cuadrícula 2D (por ejemplo, un tablero de ajedrez) donde están ocupados ciertos cuadrados y necesita colocar el número mínimo de rectángulos no superpuestos de cualquier tamaño wxh donde w = 1 o h = 1 (es decir, "cuadrado segmentos ") de modo...
Cerrado. Esta pregunta está fuera de tema . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que sea sobre el tema para el intercambio teórico de pila de informática. Cerrado hace 7 años . ¿Cómo...
Estoy impartiendo un curso sobre metaheurística y necesito generar instancias interesantes de problemas combinatorios clásicos para el término proyecto. Centrémonos en TSP. Estamos abordando gráficos de dimensión y mayores. Por supuesto, intenté generar un gráfico con una matriz de costos con...
Vi que algunas personas usan la notación de Krivine para la aplicación de funciones cuando presentan la sintaxis para el cálculo . Por ejemplo, el λ -term λ f . λ x . λ y . f x y (con la convención normal de que la aplicación de función se asocia a la izquierda, por lo que en realidad significa que...
Soy un estudiante graduado de la India. Estoy muy interesado en asistir a los talleres, conferencias y conferenciantes invitados impartidos por destacados profesores. Al final de la charla, como de costumbre, algunas personas harán preguntas y el orador las responderá. Pero mi problema es que no...
Sabemos que . Del teorema de Savitch, , y, del Teorema de la jerarquía espacial, . Entonces, como no sabemos si , no sabemos si , o sabemos que ? ¿Alguien ha intentado demostrar que \ mathcal L ^ 2 \ subseteq \ mathcal P ? ¿Cuáles son los últimos resultados o esfuerzos de esta manera? He estado...
Encontré la siguiente pregunta, que es un ejercicio fácil (spoiler a continuación). Se nos dan instancias del problema de detención (es decir ), y debemos decidir exactamente cuál de ellas se detendrá en . Es decir, necesitamos generar . Se nos da un oráculo para el problema de detención, pero...