Contar el número de coincidencias perfectas en un gráfico bipartito se puede reducir de inmediato a calcular el permanente. Dado que encontrar una coincidencia perfecta en un gráfico no bipartito está en NP, existe una reducción de los gráficos no bipartitos al permanente, pero puede implicar una...
A la luz del reciente abismo en el resultado de profundidad-3 (que entre otras cosas produce un circuito aritmético de profundidad -3 para el determinante sobre ), Tengo las siguientes preguntas: Grigoriev y Karpinski demostraron un límite inferior para cualquier circuito aritmético de...
1- ¿Hay alguna propiedad específica para la matriz de adyacencia cuando un gráfico es plano? 2- ¿Hay algo especial para calcular el permanente de la matriz de adyacencia cuando un gráfico es
Wikipedia proporciona ejemplos de problemas donde la versión de conteo es difícil, mientras que la versión de decisión es fácil. Algunos de estos están contando combinaciones perfectas, contando el número de soluciones para 222 -SAT y el número de clasificaciones topológicas. ¿Hay otras clases...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
Supongamos que se nos da una matriz n por n, M, con entradas enteras. ¿Podemos decidir en P si hay una permutación tal que para todas las permutaciones tenemos ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Π Mi π( i )ΠMETROyoσ(yo)≠ΠMETROyoπ(yo)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Observaciones Por...
Este es un seguimiento de esta pregunta y está relacionado con esta pregunta de Shiva Kinali. Parece que las pruebas en estos documentos ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) usan teoremas de jerarquía. Quiero saber si las pruebas son teoremas de diagonalización " pura...
En el documento de Ben-Dor / Halevi [1] se da otra prueba de que el permanente es -completo. En la parte posterior del documento, muestran la cadena de reducción mientras el valor permanente se conserva a lo largo de la cadena. Como el número de asignaciones satisfactorias de una fórmula 3SAT se...
Un problema importante en TCS es el problema de expresar un permanente como determinante. Estaba leyendo el artículo de Agrawal Determinante versus Permanente y en un párrafo afirma que el problema inverso es fácil. Es fácil ver que el determinante de una matriz se puede expresar como la...
Considere el siguiente problema: dada una matriz , índices i , j ∈ { 1 , ... , n } y un número entero a . Reemplazar M [ i , j ] por una y llame nueva matriz M . Es p e r ( M ) > pMETRO∈ { - m , ... , 0 , ... , m }n × nM∈{−m,…,0,…,m}n×nM\in\{-m,\dots,0,\dots,m\}^{n\times n}i , j ∈ { 1 , ... , n...
Sea una matriz o con entradas . ¿Alguien puede proporcionarme una matriz para que ? ¿Cuál es la B explícita más pequeña que se conoce de modo que \ operatorname {per} (A) = \ det (B) ? ¿Alguna referencia sobre esto con ejemplos explícitos?UNAUNAA3 × 33×33 \times 34×44 4×4 44 \times...
El algoritmo de Berkowitz proporciona un circuito de tamaño polinómico con profundidad logarítmica para determinar una matriz cuadrada utilizando potencias matriciales. El algoritmo utiliza implícitamente la cancelación. ¿Es esencial la cancelación para lograr un circuito de tamaño polinómico con...
Deje ser una matriz cuadrada dada. ¿Hay alguna evidencia de que superar los límites inferiores cuadráticos para B de modo que det ( B ) = per ( A ) pueda ser difícil?AAABBBdet(B)=per(A)det(B)=per(A)\text{det}(B) = \text{per}(A) ¿Hay alguna conjetura plausible que implique que probar límites más...
En [1] se afirma que "Sigue siendo una pregunta abierta si cada función en tiene circuitos (aunque al menos se sabe que no todas las funciones tienen circuitos uniformes DLogTime )".T C 0 # P T C 0#P#P\#PTC0TC0TC^0#P#P\#PTC0TC0TC^0 TC0TC0TC^0 circuitos generados por las funciones DLogTime no...