Resultados condicionales que implican dificultades para mejorar los límites superior / inferior para permanente

8

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?ABdet(B)=per(A)

¿Hay alguna conjetura plausible que implique que probar límites más bajos es difícil? ¿Hay alguna evidencia de que probar un filas (o columnas) límite inferior para algunos ϵ > 0 es difícil (por ejemplo, equivalente a V PV N P )?Ω(n2+ϵ)ϵ>0VPVNP

¿Hay alguna conjetura plausible que implique que probar los límites superiores es difícil? ¿Hay alguna evidencia de que la prueba de una límite superior para algunos ε ( 0 , 1 ) es difícil?O(2nϵ)ϵ(0,1)

vs
fuente
3
Creo que esta pregunta podría usar un poco más de explicación. Creo que he entendido lo que quieres decir, pero no estoy totalmente seguro.
Peter Shor
1
B
1
@SureshVenkat ¿El siguiente resultado no implica un límite inferior cuadrático? pages.cs.wisc.edu/~jyc/papers/per-det.pdf
vs
1
Bueno, ese es mi punto. Sería útil vincular a eso en la pregunta.
Suresh Venkat
@SureshVenkat ¡Oh, bien!
vs

Respuestas:

15

O(2nϵ) ϵ<1

Holger Dell, Thore Husfeldt y Martin Wahlén .

Complejidad exponencial del tiempo del polinomio permanente y del polinomio de Tutte.

Documento completo en ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

n×nO(2nϵ)×O(2nϵ)

  1. Transforme una instancia 3SAT a una permanente como en el documento anterior

  2. Transforme lo permanente en un determinante sobre la matriz más grande

  3. Calcule el determinante para encontrar el número de soluciones para la instancia original de 3SAT.

nO(2nϵ)ϵ<1ϵ

Andreas Björklund
fuente