Seja uma dada matriz quadrada. Existe alguma evidência de que ultrapassar limites inferiores quadráticos para modo que possa ser difícil?B det ( B ) = por ( A )
Existe alguma conjectura plausível que implique que provar limites mais baixos seja difícil? Existe alguma evidência de que provar um linhas (ou colunas) limite inferior para alguns seja difícil (por exemplo, equivalente a )?ϵ > 0 V P ≠ V N P
Existe alguma conjectura plausível que implique que provar os limites superiores seja difícil? Existe alguma evidência de que provar um limite superior de para alguns seja difícil?ϵ ∈ ( 0 , 1 )
Respostas:
Um limite superior de pode não ser possível para qualquer , a menos que a Hipótese de tempo exponencial (ETH) seja falsa, consulteϵ < 1O(2nϵ) ϵ<1
Ou seja, se a incorporação da permanente em um determinante do tamanho for rápida o suficiente, você poderiaO ( 2 n ϵ ) × O ( 2 n ϵ )n×n O(2nϵ)×O(2nϵ)
Transforme uma instância 3SAT em uma permanente, como no artigo acima
Transforme a permanente em determinante sobre a matriz maior
Calcule o determinante para encontrar o número de soluções para a instância 3SAT original.
O tempo de execução para uma instância 3SAT com variação seria para alguns dependendo de se a etapa (2) for rápida o suficiente (digamos polinomial em n para cada entrada da matriz maior). Isso contradiz o ETH.O ( 2 n ε ' ) ε ' < 1 εn O(2nϵ′) ϵ′<1 ϵ
fonte