Cosas

´ PROBLEMAS DE CONTEO A TRAVES DE MONTE CARLO

1.

PROBLEMAS DE CONTEO

Muchos de los problemas importantes de la ciencia y las matem´ticas a 1 es lidiar con problemas de conteo que son #P − complete . Este es un concepto relacionado con la clase de familias de problemas NP-hard 2 . Estos son algunos ejemplos de problemas de conteo #P − complete: Problema de conteo del ciclo Hamiltonian:Problema de encontrar un ciclo hamiltoniano en particular es un caso especial de la TSP3 en el que las distancias entre el nodo adyacente son 1, y otras distancias son 0, y el objetivo es encontrar el recorrido m´s largo. a El Problema de self-avoiding walk: ‘¿Cu´ntos paseos de una cierta longia tud n, que partiendo del origen, se mueven entre los puntos de cuadr´ ıcula m´s cercanas sin visitar elmismo punto de la cuadr´ a ıcula m´s tan a una vez‘? Problema de conteo satisfiability SAT. Sea x = {x1 , ....., xn } una colecci´n de variables booleanas.Sea C un conjunto de cl´usulas booleanas. o a Ejemplos de este tipo de cl´usulas son x1 ∨ x2 y (x1 ∨ x2 ) ∧ (¯1 ∨ x2 ) a ¯ ¯ x Esto es, de cu´ntas maneras posibles se puede establecer las variables a para que cada cl´usula C sea cierta. a Otrosproblemas de #P − complete incluyen el recuento del n´mero de u coincidencias perfectas en un gr´fico bipartito, la determinaci´n de la pera o manente de una matriz, contando el n´mero de grupos de tama˜o fijo en un u n gr´fico, y contando el n´mero de arboles en un gr´fico. En este trabajo se a u a muestra como el conteo de #P −complete puede ser visto como un caso especial de problema de estimaci´n, ycomo tal puede ser resuelto eficientemente o utilizando t´cnicas de Monte Carlo , tales como el muestreo de importancia e y MCMC 4 .
”Es el conjunto de los problemas de conteo que pertenecen a #P” ”Es el conjunto de los problemas de decisi´n que contiene los problemas H tales que o todo problema L en NP puede ser transformado polinomialmente en H” 3 ”Travelling Salesman Problem” 4 ”MCMC es unat´cnica que simula una cadena de Markov cuyos estados siguen una e probabilidad dada en un estado de espacios de grandes dimensiones”
2 1

1

2.

PROBLEMA SATISFIABILITY

El problema satisfiability booleana SAT juega un papel central en la optimizaci´n combinatoria y, en particular, en la integridad NP. Cualquier o problema NP-completo, tal como problema de corte m´ximo, el problema agraph-coloring, y el TSP, se pueden traducir en un problema SAT de tiempo polinomial. El problema SAT desempe˜a un papel central en la soluci´n de n o problemas a gran escala computacional, tales como la planificaci´n y la proo gramaci´n, dise˜o de circuitos integrados, dise˜o de arquitectura, infograf´ o n n ıa, procesamiento de im´genes, y encontrar el estado plegado de una prote´ a ına. Hay diferentesformulaciones para el problema SAT, pero la m´s com´n es a u el que se presenta a continuaci´n, consta de dos componentes: o Sean x1 , ..., xn , un conjunto de n variables booleanas que representa los estados que pueden ser T RU E(= 1) o F ALSE(= 0). La negaci´n o l´gica de una variable x se denota x. Por ejemplo T RU E = F ALSE. o ¯ Una variable o su negaci´n se llama un literal o Un conjunto dem cl´usulas distintas C1 , C2 , ........, Cm de la forma Ci = a zi1 ∨ zi2 ∨ .... ∨ zik , donde la z s son literales y ∨ denota el operador l´gico OR. Por ejemplo, 0 ∨ 1 = 1. o El vector binario x = (x1 , ..., xn ) se llama una asignaci´n de verdad, o simo plemente una asignaci´n. As´ xi = 1 asigna verdad a xi , y xi = 0 asigna o ı, verdad a xi para cada i = 1, ..., n. El problema SAT simple ahorase puede ¯ formular como: Encontrar una asignaci´n de verdad x de tal manera que o todas las cl´usulas sean verdaderas. a Denotando a y como el operador l´gico ∧, podemos representar el proo blema anterior SAT a trav´s de una f´rmula unica como e o ´ F1 = C1 ∧ ..... ∧ Cm Donde {Ck } consta de literales conectados s´lo con los operadores ∨. Se dice o que la f´rmula SAT est´ en forma normal...