Análise matemática e complexidade computacional?

a complexidade computacional envolve grandes quantidades de combinatória e teoria dos números, algumas ingridiências da estocástica e uma quantidade emergente de álgebra.

No entanto, como analista, pergunto-me se existem aplicações de análise nesse campo, ou talvez idéias inspiradas pela análise. Tudo o que sei que corresponde ligeiramente a isso é a transformação de Fourier em grupos finitos.

Pode me ajudar?

Flajolet e Sedgewick publicaram o livro "Analytic Combinatorics" http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html . Não sei muito sobre esse tópico, mas as pessoas no campo usam ferramentas de análises complexas. Até agora, suas aplicações parecem mais na análise de algoritmos, não na complexidade computacional, tanto quanto eu vejo.

Os algoritmos de Markov Chain Monte Carlo são uma ferramenta útil para encontrar algoritmos de aproximação. Algumas técnicas para mostrar que essas cadeias de Markov se misturam são inspiradas ou vêm diretamente da análise - por exemplo, veja o capítulo sobre estimativa do volume de um corpo convexo no livro de Mark Jerrum sobre contagem .

Existem abordagens analíticas para o lema de Szemerédi, que tem uma aplicação atraente para o teste combinatório de propriedades. O Lema de Szemerédi para o analista possui um algoritmo aleatório para encontrar uma partição fracamente regular de um gráfico; veja também Limites de gráfico e teste de parâmetros .

A análise funcional está desempenhando um papel cada vez mais importante na teoria dos incorporamentos métricos. Embora seja difícil enumerar todos os aspectos da interação, o tema principal é o uso de métodos da análise funcional para entender como as métricas são incorporadas aos espaços normatizados. Esse último problema surge no problema de corte mais escasso, que é um importante problema de otimização de gráfico.

Para mais informações, uma boa fonte é qualquer coisa de Assaf Naor .

Não é sobre complexidade computacional, mas interessante, no entanto

Algumas abordagens para a semântica da computação infinita são baseadas em espaços métricos. Pesquisando no Google "semântica do espaço métrico" aparece bastante. Uma referência (antiga) sobre o tópico é a Control Flow Semantics de Bakker e de Vink. Alguns trabalhos recentes foram realizados por nosso próprio Neel , a saber, Semântica Ultramétrica para Programas Reativos . A área é muito diferente das descritas acima, mas os conceitos da análise certamente encontram um lar aqui.

A teoria das medidas limitadas por recursos, desenvolvida por Jack Lutz, é uma excelente área para as pessoas com experiência em análise. O artigo original

Quase em toda parte, alta complexidade não uniforme , Jack H. Lutz, Jornal de Ciências de Computadores e Sistemas, 1992.

generalizar a noção de medida de Lebesgue em classes de complexidade, e muitos trabalhos a seguir podem ser encontrados na internet.

$\mathsf{P}$$\mathsf{NP}$$\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{ESPACE}$$\Omega(2^n/n)$$\mathsf{ESPACE}$

Pessoas que trabalham em diferentes áreas da ciência da computação podem se beneficiar de vários subcampos de análise.

Para dar um exemplo concreto, descreverei meu próprio caso. Estou realizando pesquisas em fundações de criptografia. Nesse campo (assim como na complexidade computacional), existe um construto chamado oráculo aleatório (veja também esta página ). Às vezes, suas várias propriedades são estudadas explorando ferramentas da teoria da medida , que é um subcampo da análise. Esse tratamento pode ser encontrado neste artigo , bem como em vários artigos que o citam.

Você também pode dar uma olhada em Noções básicas de álgebra e análise para ciência da computação, por Jean Gallier. É um livro em andamento e informa as novidades no campo.

Acredito que a melhor conexão entre análise matemática e teoria da complexidade está no modelo de computação real de Blum et al. Ainda é um problema em aberto separar NP_R de P_R, onde as duas classes são definidas no modelo de computação real, no qual todo número real é uma entidade e uma operação regular (+, -, *, /) dá um passo.