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?
¿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 P ≠ V N P )?
¿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?
Respuestas:
Transforme una instancia 3SAT a una permanente como en el documento anterior
Transforme lo permanente en un determinante sobre la matriz más grande
Calcule el determinante para encontrar el número de soluciones para la instancia original de 3SAT.
fuente