Resultados condicionais implicando dificuldade em melhorar os limites superior / inferior para

8

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 )ABdet(B)=per(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 PV N PΩ(n2+ϵ)ϵ>0VPVNP

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 )O(2nϵ)ϵ(0,1)

vs
fonte
3
Eu acho que essa pergunta poderia usar um pouco mais de explicação. Acredito que tenha entendido o que você quer dizer, mas não tenho certeza.
quer
1
Existe uma referência para o "limite inferior quadrático de tal que det (B) = por (A)"? B
Suresh Venkat
1
@SureshVenkat O resultado a seguir não implica um limite inferior quadrático? pages.cs.wisc.edu/~jyc/papers/per-det.pdf
vs
1
Bem, esse é o meu ponto. seria útil vincular isso à pergunta.
perfil completo de Suresh Venkat
@SureshVenkat Oh Ok!
vs

Respostas:

15

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

Holger Dell, Thore Husfeldt e Martin Wahlén .

Complexidade exponencial do tempo do polinômio permanente e do Tutte.

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

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×nO(2nϵ)×O(2nϵ)

  1. Transforme uma instância 3SAT em uma permanente, como no artigo acima

  2. Transforme a permanente em determinante sobre a matriz maior

  3. 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 εnO(2nϵ)ϵ<1ϵ

Andreas Björklund
fonte