Preguntas etiquetadas con randomized-algorithms

Estaba leyendo CLRS y me pidió que mostrara que si es un primo de la forma y era un residuo cuadrático, entonces es una raíz cuadrada (también se puede mostrar fácilmente que es una raíz cuadrada).ppp4k+34k+34k+3aaaak+1ak+1a^{k+1}a−ka−ka^{-k} Me preguntaba si usar el hecho anterior y también que...

Pruebas de identidad polinomio es el ejemplo típico de un problema conocido para estar en co-RP , pero no se sabe que en P . Sobre los circuitos aritméticos , de hecho parece difícil, ya que el grado del polinomio puede hacerse exponencialmente grande mediante la cuadratura repetida. Esta pregunta...

A partir de, las pruebas por el método probabilístico a menudo se dice que no son constructivas. Sin embargo, una prueba por método probabilístico de hecho diseña un algoritmo aleatorio y lo usa para probar la existencia. Citado de p103 de Algoritmos aleatorizados por Rajeev Motwani, Prabhakar...

Existe un algoritmo aleatorio muy simple que, dado un 3SAT, produce una asignación que satisface al menos 7/8 de las cláusulas (en expectativa): elija una asignación aleatoria. Una asignación aleatoria satisface cada cláusula con probabilidad 7/8, por lo que la linealidad de la expectativa muestra...