Noção alternativa de complexidade baseada na diferença entre a força bruta e o melhor algoritmo?

Normalmente, algoritmos eficientes têm um tempo de execução polinomial e um espaço de solução exponencialmente grande. Isso significa que o problema deve ser fácil em dois sentidos: primeiro, o problema pode ser resolvido em um número polinomial de etapas e, segundo, o espaço da solução deve ser muito estruturado, pois o tempo de execução é apenas polilogarítmico no número de soluções possíveis.

No entanto, algumas vezes essas duas noções divergem, e um problema é fácil apenas no primeiro sentido. Por exemplo, uma técnica comum em algoritmos de aproximação e complexidade parametrizada é (aproximadamente) provar que o espaço da solução pode realmente ser restrito a um tamanho muito menor que a definição ingênua e, em seguida, usar força bruta para encontrar a melhor resposta nesse espaço restrito . Se, a priori , podemos nos restringir a, digamos, n ^ 3 respostas possíveis, mas ainda precisamos verificar cada uma delas, então, em certo sentido, esses problemas ainda são "difíceis", pois não há algoritmo melhor que a força bruta.

Por outro lado, se tivermos um problema com um número duplamente exponencial de respostas possíveis, mas pudermos resolvê-lo apenas em um tempo exponencial, gostaria de dizer que esse problema é "fácil" ("estruturado" pode ser melhor word), já que o tempo de execução é apenas o log do tamanho do espaço da solução.

Alguém conhece algum artigo que considere algo como dureza com base na diferença entre um algoritmo eficiente e força bruta ou dureza em relação ao tamanho do espaço da solução?

Um problema para formalizar a pergunta é que a frase "espaço de solução para o Problema A" não está bem definida. A definição de um espaço de solução precisa de um algoritmo verificador que, dada uma instância e uma solução candidata, verifique se a solução está correta ou não. Em seguida, o espaço da solução de uma instância gravada em um verificador é o conjunto de soluções candidatas que tornam a saída do verificador "correta".

Por exemplo, considere o problema SAT0: dada uma fórmula booleana, ela é satisfeita pela atribuição de todos os zeros? Esse problema ocorre trivialmente no tempo polinomial, mas seu espaço de solução pode variar bastante, dependendo do verificador usado. Se o seu verificador ignora a solução candidata e apenas verifica se todos os zeros funcionam na instância, o "espaço da solução" para qualquer instância SAT0 nesse verificador é trivial: todas as soluções são possíveis. Se o seu verificador verificar se a solução candidata é uma atribuição satisfatória, o espaço da solução de uma instância SAT0 pode realmente ser bastante complexo, sem dúvida tão complexo quanto o espaço de solução de qualquer instância SAT0.

Dito isto, o problema de "evitar a busca por força bruta" pode ser formalizado da seguinte maneira (como visto no artigo "Melhorar a busca exaustiva implica limites inferiores superpolinomiais"). Você recebe um algoritmo de verificação que é executado no tempo , em instâncias de tamanho n e em soluções candidatas de k bits. A questão é, * em instâncias arbitrárias de tamanho n , podemos determinar se existe uma solução correta (escreva este verificador) com no máximo k bits, em muito menos do que tempo O ( 2 k t ( n , k ) ) ?$t(n,k)$$n$$k$$n$$k$$O(2^k t(n,k))$

Nota é o custo de tentar todas as cadeias de comprimento até ke executar o verificador. Portanto, o que foi dito acima pode ser perguntado se podemos melhorar a pesquisa de força bruta para o verificador fornecido. A área de "algoritmos exatos para problemas difíceis de NP" pode ser vista como um esforço de longo prazo para estudar a dificuldade de melhorar a pesquisa de força bruta para determinados verificadores muito naturais: por exemplo, a questão de encontrar algoritmos melhores que 2 n para SAT é a questão de saber sempre se podemos melhorar a pesquisa de força bruta pelo verificador que verifica se a solução candidata especificada é uma atribuição satisfatória para a instância SAT especificada.$O(2^k t(n,k))$$2^n$

O artigo mostra algumas conseqüências interessantes de melhorar a busca por força bruta para alguns problemas. Mesmo melhorar a busca por força bruta por "espaços de solução de tamanho polinomial" teria consequências interessantes.

Como você lida com problemas típicos de programação dinâmica? Aqui, o que acontece com frequência é que o espaço das soluções ideais é polinomialmente limitado, mas o espaço das soluções não. Portanto, parece "fácil" no seu sentido, porque o tempo de execução é logarítmico no espaço da solução, mas é "difícil" no seu sentido, porque executa a "força bruta" em todas as soluções potencialmente ideais.

A perspectiva parece assumir algumas coisas, como fininidade de espaços de solução.

Por exemplo, pense no problema de gerar um mosaico de Voronoi a partir de um conjunto de pontos de entrada. Aqui há um espaço de solução com tamanho infinito, pois cada ponto nas bordas do diagrama é uma tupla de números reais. No entanto, uma solução pode ser alcançada em O (n log (n)) no número de pontos de entrada (para o plano).

Relacionada são problemas que admitem algoritmos com atraso polinomial . A primeira solução e todas as soluções subsequentes podem ser geradas em tempo polinomial. Johnson, Yannakakis e Papdimitriou discutem essa estrutura no contexto de outras possíveis lacunas (como o tempo total polinomial): Sobre a geração de todos os conjuntos independentes máximos , Information Processing Letters 27 , 119-123, 1988.