Preguntas etiquetadas con counting-complexity

15
Descomposición de gráficos para combinar funciones "locales" de etiquetado de vértices

Supongamos que queremos encontrar o max x ∏ i j ∈ E f(xi,xj)∑x∏ij∈Ef(xi,xj)∑x∏ij∈Ef(xi,xj)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏ij∈Ef(xi,xj)maxx∏ij∈Ef(xi,xj)\max_x \prod_{ij \in E} f(x_i,x_j) Donde Max o la suma se toma sobre todos los marcajes de VVV , el producto se toma sobre todos los...

14
¿Es la equivalencia eta para funciones compatible con la operación seq de Haskell?

Lema: Suponiendo equivalencia eta tenemos eso (\x -> ⊥) = ⊥ :: A -> B. Prueba: ⊥ = (\x -> ⊥ x)por equivalencia eta y (\x -> ⊥ x) = (\x -> ⊥)por reducción bajo la lambda. El informe Haskell 2010, sección 6.2 especifica la seqfunción mediante dos ecuaciones: seq :: a -> b ->...

13
Paridad-L vs.LN

Parity-L, también conocido como L, es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación". Niel de Beaudrap hizo una pregunta relacionada reciente .⊕⊕\oplus Mi pregunta es la...