A lo que me refiero como contar es el problema que consiste en encontrar el número de soluciones para una función. Más precisamente, dada una función F: N→ { 0 , 1 }F:norte→{0 0,1}f:N\to \{0,1\} (no necesariamente caja negra), aproximada # { x ∈ N∣ f( x ) = 1 } = | F-...
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...
Esta pregunta está motivada por una pregunta de MathOverflow de Peng Zhang . Valiant mostró que contar las camarillas máximas en un gráfico general es # P-completo, pero ¿qué pasa si restringimos a los gráficos de incomparabilidad (es decir, queremos contar las antichains máximas en un grupo...
Deje que G sea un gráfico conectado. ¿Cuál es la complejidad de contar todos los subgrafos conectados si G es de los siguientes tipos? G es general. G es plano. G es bipartito. No me importan las estructuras o ... ¡solo necesito contar todas las subgrafías conectadas! También estoy...
Tengo parte de un intento de prueba de . El intento de prueba consiste en una reducción de Karp desde -complete problem 3-REGULAR VERTEX COVER a SAT. ⊕ P ⊕⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Dado un gráfico cúbico , la reducción genera una fórmula CNF que...
Por http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Si es un lenguaje de PSPACE completa, P A = N P A .UNAAPAGUN= NPAGUNPA=NPAP^{A}=NP^{A} Si es un oráculo de tiempo polinómico determinista, P B ≠ N P B (suponiendo P ≠ N P ).siBBPAGsi≠ NPAGsiPB≠NPBP^{B}\ne NP^{B}PAG≠ NPAGP≠NPP\ne NP...
Dado un gráfico dirigido con n nodos de modo que cada vértice tenga exactamente dos bordes salientes, y un número natural N codificado en binario, dos vértices syt, Quiero contar el número de rutas (no necesariamente simples) de sa t en N pasos. ¿Es este un problema difícil de # P? O, en...
¿Qué se sabe sobre la transición de fase en problemas # P-Complete? Específicamente, ¿existe una transición de fase diferente para # DNF-k-SAT y # CNF-k-SAT? Actualización: Como sabemos, hay una transición de fase en Random k-SAT donde la resolución del problema pasa de ser fácil a difícil y...
Para un problema de búsqueda local polinómica , sabemos que debe existir al menos una solución (óptimo local). Sin embargo, podrían existir muchas más soluciones, ¿qué tan difícil es contar la cantidad de soluciones para un problema PLS completo? Estoy particularmente interesado en el problema de...
Supongo que se llamaría # P-Space, pero solo he encontrado un artículo que lo menciona vagamente. ¿Qué tal la versión de conteo de EXP-TIME-Complete, NEXP-Complete y EXP-SPACE-Complete? ¿Hay algún trabajo previo que pueda citarse con respecto a este o algún tipo de inclusión o exclusión como el...
En una fórmula CNF de lectura dos veces opuesta, cada variable aparece dos veces, una vez positiva y otra negativa. Estoy interesado en el problema , que consiste en calcular la paridad del número de asignaciones satisfactorias de una fórmula CNF de lectura dos veces
Esta pregunta ha surgido en mi mente después de leer las contribuciones de András Salamon y Colin McQuillan a mi pregunta anterior Soluciones de conteo de fórmulas Monotone-2CNF . EDITAR 30 ª Mar 2011 pregunta Agregado n ° 2. EDITAR 29 º Oct 2010 Pregunta reformuló después de la propuesta...
PREGUNTA CORTA: ¿MAJ-3CNF es un problema de PP completo bajo muchas reducciones? VERSIÓN MÁS LARGA: Es bien sabido que MAJSAT (decidir si la mayoría de las asignaciones de oración proposicional satisface la oración) es PP-completo bajo muchas reducciones y #SAT es # P-completo bajo reducciones...
Estoy interesado en el siguiente problema. Se nos da como entrada una "permutación de destino" , así como una lista ordenada de índices . Luego, comenzando con la lista (es decir, la permutación de identidad), en cada paso de tiempo intercambiamos el elemento en con el elemento, con probabilidad...
Estaba revisando el trabajo seminal de Les Valiant y tuve un momento difícil con la Proposición 4.3 en la página 10 del documento. No puedo ver por qué es el caso que si hay un generador con ciertos valores para con una base { ( a 1 , b 1 ) ... ( a r , b r ) } , entonces existe algún generador con...
Considere el problema clásico # P-complete # 3SAT, es decir, contar el número de valoraciones para hacer que un 3CNF con nnn variables sea satisfactoria. Estoy interesado en la aproximabilidad aditiva . Claramente, hay un algoritmo trivial para lograr2n−12n−12^{n-1}error 2 n - 1 , pero...
Un homomorfismo de un gráfico a un gráfico G ′ = ( V ′ , E ′ ) es un mapeo f de V a V ′ tal que si x e y son adyacentes en E entonces f ( x ) y f ( y ) son adyacentes en E ' . Un endomorfismo de un gráfico GG=(V,E)G=(V,E)G = (V, E)G′=(V′,E′)G′=(V′,E′)G' = (V',...
Deje ser un gráfico. Dejeser un número entero Sea el número de inducidas por aristas de tienen vértices y un número impar de aristas. Sea el número de inducidas por aristas de tienen vértices y un número par de aristas. Deje . El problema ODD EVEN DELTA consiste en calcular , dados y .G = ( V,...
Considere una fórmula Monotone 3CNF que tenga las siguientes restricciones adicionales: Cada variable aparece exactamente en cláusulas.222 Dadas cláusulas, comparten como máximo variable.222111 Me gustaría saber qué tan difícil es contar las tareas satisfactorias de tal...
En una pregunta anterior Algoritmo parametrizado para encontrar bicliques , pregunté si había algoritmos parametrizados rápidos para encontrar un -biclique en un gráfico de n vértices y aprendí que estaba abierto si es FPT wrt k . ¿Es lo mismo para contar las k × k -bicliques, o se sabe que esto es...