Ciencias de la Computación

15
¿Puede haber un algoritmo de ajedrez perfecto?

Los algoritmos de ajedrez actuales van alrededor de 1 o tal vez 2 niveles por un árbol de posibles caminos dependiendo de los movimientos del jugador y del oponente. Digamos que tenemos el poder informático para desarrollar un algoritmo que predice todos los movimientos posibles del oponente en un...

15
Si P = NP, ¿por qué

Aparentemente, si P=NPP=NP{\sf P}={\sf NP} , todos los idiomas en PP{\sf P} excepto ∅∅\emptyset y Σ∗Σ∗\Sigma^* serían NPNP{\sf NP} -completos. ¿Por qué estos dos idiomas en particular? ¿No podemos reducir a ellos otro lenguaje en PP{\sf P} al enviarlos al aceptar o no...

15
¿Está completo el NP de Hidoku?

Un Hidoku es una cuadrícula con algunos enteros precompletados de 1 a n 2 . El objetivo es encontrar un camino de enteros sucesivos (de 1 an×nn×nn \times nn2n2n^2 ) en la cuadrícula. Más concretamente, cada celda de la cuadrícula debe contener un número entero diferente de 1 a n 2 y cada celda con...

15
¿Quiénes son los legisladores de Paxos?

En el documento seminal de sistemas distribuidos The Part Time Parliament (el protocolo de Paxos), Leslie Lamport nombra legisladores ficticios que participan en el protocolo del parlamento de Paxon. Según este escrito , señala que: Les di a los legisladores griegos los nombres de los...

15
¿Para qué se utilizan las celosías?

Wikipedia dice : Las redes completas aparecen en muchas aplicaciones en matemáticas y ciencias de la computación. ¿Se refiere solo al hecho de que el álgebra booleana estándar utilizada en el cálculo es una red completa? ¿Hay algo que ganemos al trabajar en el nivel abstracto de celosías en...

15
Problemas de decisión en

¿Cuáles son algunos ejemplos de problemas de decisión difíciles que se pueden resolver en tiempo polinómico? Estoy buscando problemas para los cuales el algoritmo óptimo es "lento", o problemas para los cuales el algoritmo más rápido conocido es "lento". Aquí hay dos ejemplos: Reconocimiento de...

15
¿Cómo implementar dos pilas en una matriz?

Quiero comenzar diciendo que esta NO es una pregunta de tarea. Estoy leyendo Introducción a los algoritmos, el famoso texto CLRS para ser un mejor programador. Estoy tratando de resolver los problemas y ejercicios dados en el libro por mí mismo. Estoy tratando de resolver el Ejercicio 10.1-2 del...