Existe um algoritmo subcúbico para o seguinte problema?

$n \times n$$A=(a_{ij})$

Existe uma abordagem bastante prática que funciona em , em que é o número de bits na palavra do processador. A idéia principal é que você itere sobre os elementos da matriz um por um na ordem crescente (rompe arbitrariamente) e "os liga". Considere o momento em que o elemento maior de alguns triplos está ativado. Para simplificar, vamos assumir que o referido elemento é . É natural adicionar o valor do triplo à resposta agora, quando o último elemento estiver ativado. Portanto, temos que contar o número de possíveis , de modo que e$O(n^3 / w)$$w$$a_{ij}, a_{ik}, a_{jk}$$a_{ij}$$k$$a_{ik}$$a_{jk}$já estão ativados (esse seria o número de triplos, aqui é o maior elemento, portanto, eles foram completamente ativados agora). Aqui, podemos acelerar a implementação ingênua de usando a otimização de bits.$a_{ij}$$O(n)$

Para obter detalhes, você pode consultar a seguinte implementação no C ++ 11 que deve funcionar para , (não é muito otimizado; no entanto, ainda supera o somatório ingênuo de por grande margem, pelo menos na minha máquina).$n \leqslant 5000$$|a_{ij}| \leqslant 10^9$$n = 5000$

// code is not very elegant, 
// but should be understandable
// here the matrix a has dimensions n x n
// a has to be symmetric!
int64_t solve (int n, const vector<vector<int32_t>> &a)
{
        std::vector<boost::dynamic_bitset<int64_t>> mat
        (n, boost::dynamic_bitset<int64_t>(n));

        vector<pair<int, int>> order;
        for (int j = 1; j < n; j++)
        for (int i = 0; i < j; i++)
            order.emplace_back(i, j);
        sort(order.begin(), order.end(),
            [&] (const pair<int, int> &l, const pair<int, int> &r) 
            {return a[l.first][l.second] < a[r.first][r.second];});

        int64_t ans = 0;
        for (const auto &position : order)
        {
            int i, j;
            tie (i, j) = position;
            mat[i][j] = mat[j][i] = 1;
            // here it is important that conditions 
            // mat[i][i] = 0 and mat[j][j] = 0 always hold
            ans += (mat[i] & mat[j]).count() * int64_t(a[i][j]);
        }

        return ans;
}

Se você considerar o uso de trapaça nas otimizações de bits, poderá usar o método quatro russos para o mesmo resultado aqui, produzindo um algoritmo , que deve ser menos prático (porque é bastante grande no hardware mais moderno) mas é teoricamente melhor. De fato, vamos escolher e manter cada linha da matriz como uma matriz de inteiros de a , onde o ésimo número em a matriz corresponde aos bits da linha que variam de inclusivo a exclusivo em$O(n^3 / \log n)$$w$$b \approx \log_2 n$$\lceil \frac{n}{b} \rceil$$0$$2^b - 1$$i$$ib$$\min(n, (i + 1)b)$$0$-indexação. Podemos pré-calcular os produtos escalares de cada dois desses blocos no tempo . A atualização de uma posição na matriz é rápida porque estamos alterando apenas um número inteiro. Para encontrar o produto escalar de linhas e apenas iterar sobre matrizes correspondente a esse linhas, procure produtos escalares dos blocos correspondentes na tabela e resumir os produtos obtidos.$O(2^{2b} b)$$i$$j$

O parágrafo acima pressupõe que operações com números inteiros levam tempo . É uma suposição bastante comum , porque geralmente não altera a velocidade comparativa dos algoritmos (por exemplo, se não usarmos essa suposição, o método da força bruta realmente funciona no tempo (aqui medimos o tempo em operações de bit) se receber valores inteiros com valores absolutos pelo menos até para algumas constantes (e caso contrário, podemos resolver o problema com multiplicações de matriz de qualquer maneira); no entanto, o método dos quatro russos sugerido acima usa$\leqslant n$$O(1)$$O(n^3 \log n)$$a_{ij}$$n^{\varepsilon}$$\varepsilon > 0$$O(n^{\varepsilon})$$O(n^3 / \log n)$ operações com números de tamanho nesse caso; portanto, ele faz operações de bits, o que ainda é melhor que a força bruta, apesar da mudança do modelo).$O(\log n)$$O(n^3)$

A questão sobre a existência da abordagem ainda é interessante, no entanto.$O(n^{3 - \varepsilon})$

As técnicas (otimizações de bits e método dos quatro russos) apresentadas nesta resposta não são de forma alguma originais e são apresentadas aqui para a completude da exposição. No entanto, encontrar uma maneira de aplicá-las não era trivial.