Análise complexa em ciência da computação teórica

24

Existem muitas aplicações de análises reais em ciência da computação teórica, cobrindo testes de propriedades, complexidade da comunicação, aprendizado do PAC e muitos outros campos de pesquisa. No entanto, não consigo pensar em nenhum resultado no TCS que dependa de análises complexas (fora da computação quântica, onde números complexos são intrínsecos ao modelo). Alguém tem um exemplo de um resultado clássico do TCS que usa análise complexa?

soft-question big-picture
fonte

11

Ótima pergunta! Eu sugeriria que seria melhor excluir resultados relacionados à teoria dos números - por exemplo, qualquer uso da hipótese de Riemann - em vez da computação quântica, que tende a ser sobre sistemas de dimensão finita (tanto quanto eu sei).

Colin McQuillan

11

Utilizamos análises complexas em um artigo "A constante de Grothendieck é estritamente menor que a de Krivine", que (do ponto de vista do TCS) fornece um algoritmo de aproximação para o problema de maximizar

\sum_{i, j} a_{i j} x_{i} y_{j}

$\sum_{i,j} a_{ij} x_i y_j$ sujeito a

x_{i}, y_{j} \in {\pm 1}

$x_i, y_j\in \{\pm 1\}$ . Veja ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf

Yury

3

@ Yury que poderia muito bem ser uma resposta.

Suresh Venkat

14

O algoritmo baseado em complexo de Barvinok para aproximar os algoritmos de tempo polinomial permanente para aproximar permanentes e discriminantes mistos dentro de um fator simplesmente exponencial .

Além disso, obviamente, operadores complexos (e algumas análises complexas) são importantes na computação quântica.

Deixe-me recomendar também este livro: Tópicos em análise de desempenho de Eitan Bachmat com muitas questões relevantes e outras coisas importantes.

Gil Kalai
fonte

Esse é um ótimo exemplo, eu não estava ciente desse resultado - obrigado!

25

Não é um problema único, mas todo o campo da combinatória analítica (veja o livro de Flajolet e Sedgewick ) explora como analisar a complexidade combinatória de estruturas de ~~contagem~~ (ou mesmo tempos de execução de algoritmos) escrevendo uma função geradora apropriada e analisando a estrutura das soluções complexas.

Suresh Venkat
fonte

Oi Suresh, o que você quer dizer com 'analisar a complexidade'?

Andy Drucker

2

Ah, eu escrevi errado. Eu quis dizer "analisar a complexidade combinatória das estruturas" - será corrigido.

precisa saber é o seguinte

15

Jon Kelner ganhou o STOC Best Student Paper Award em 2004 por seu artigo "Particionamento espectral, limites de autovalores e embalagens circulares para gráficos de gênero limitado"

Vou apenas citar o resumo:

Como nosso principal lema técnico, provamos um O (g / n) vinculado ao segundo menor autovalor do Laplaciano de tais gráficos e mostramos que isso é rigoroso, resolvendo assim uma conjectura de Spielman e Teng. Embora esse lema seja essencialmente de natureza combinatória, sua prova vem da matemática contínua, baseando-se na teoria das embalagens circulares e na geometria das superfícies compactas de Riemann.

O uso de análises complexas (e outras matemáticas "contínuas") para atacar problemas "tradicionais" do separador de gráficos foi memorável e é a principal razão pela qual esse artigo ficou na minha cabeça, apesar de não estar totalmente relacionado à minha pesquisa.

Mugizi Rwebangira
fonte

8

Eu acho que você pode estar mais interessado em análises complexas usadas diretamente na prova. No entanto, aqui estão dois exemplos de uma classe de Algoritmos de nível de pós-graduação em que estou participando:

a) Transformação rápida de Fourier, por exemplo, usada na multiplicação polinomial. Embora a implementação possa ser feita com módulo aritmético ou ponto flutuante (e algumas análises aritméticas), a prova é melhor compreendida em termos de números complexos e suas raízes de unidade. Não mergulhei no assunto, mas estou ciente de que a FFT tem uma ampla gama de aplicações.

b) Em geral, equipar o modelo de RAM com a capacidade de lidar com números complexos em tempo constante (as partes reais e imaginárias ainda têm precisão finita) permite codificar de forma inteligente os problemas e explorar as propriedades dos números complexos que podem revelar uma solução (consulte também os comentários sobre por que isso não permitirá que você seja mais rápido).

chazisop
fonte

Você tem um exemplo da segunda observação? É trivial adicionar uma classe "complexo inteiro de O (log n) bits" à RAM padrão com operações em tempo constante. Ou por "mais rápido", você quer dizer "mais rápido por um fator de 2"?

Jeffε

Este foi um exercício da palestra: "Suponha que você esteja lidando com uma RAM estendida que pode calcular números complexos a um custo unitário por multiplicação, divisão, adição e subtração. Além disso, também pode calcular o valor absoluto | c | de um número complexo c em tempo unitário.Além disso, “conhece” as constantes complexas 0, 1 e I. Mostre que, dado um número inteiro positivo n em uma RAM estendida, o número n! pode ser calculado em

tempo. A solução usa multiplicação polinomial, pelo que sei é mais rápida que o modelo de RAM padrão.

O (\sqrt{n} \log^{2} n)

$O( \sqrt{n} \log ^{2} n)$

chazisop

6

O algoritmo proposto requer aritmética real de precisão infinita em tempo constante. (Você não pode calcular um número inteiro de

em

tempo usando uma máquina com palavras em

, porque você nem teria tempo para escrever a saída!) A pergunta está pedindo para você adicionar raízes quadradas ao modelo de RAM real, e não números complexos por si só.

Ω (n \log n)

$\Omega(n\log n)$

o (n)

$o(n)$

O (\log n)

$O(\log n)$

Jeffε

Obrigado pelo comentário, é muito esclarecedor. Eu acho que devo atualizar minha resposta para a parte de codificar apenas um problema com números complexos, ou seja, para encontrar uma solução que você perderia de outra forma.

chazisop

6

Talvez esse aplicativo esteja entre o TCS e o Disc math, mas fiquei um pouco surpreso ao ler o artigo "Sobre as funções booleanas dobradas, que são simétricas" de Petr Savicky (http://www2.cs.cas.cz/~savicky/ papers / symmetric.ps). Os teoremas são apenas relativos a funções booleanas, no entanto, uma das provas usa números complexos.

Magnus Find
fonte

5

Utilizamos o Teorema de Resíduos de Cauchy a partir de análises complexas como a principal ferramenta técnica em nosso artigo " Aproximando Predicados de Limiar Linear ".

MCH
fonte

5

O teorema de empacotamento circular de Koebe-Andreev-Thurston é originado no teorema do mapeamento de Riemann e possui vários aspectos algorítmicos. Por exemplo, ele fornece uma prova do teorema do imperador Lipton-Tarjan para gráficos planares.

Gil Kalai
fonte

5

Fresco do forno:

Um algoritmo de tempo polinomial para recuperação de populações com perdas Por: Ankur Moitra, Michael Saks

Citando o artigo: "Aqui provaremos o princípio da incerteza declarado na seção anterior usando ferramentas de análise complexa. Talvez um dos teoremas mais úteis na compreensão da taxa de crescimento das funções holomorfas no plano complexo seja o Teorema dos Três Círculos de Hadamard. .. "

Gil Kalai
fonte

σ

$\sigma$

p (0) - ϵ ‖ p ‖_{1}

$p(0) - \epsilon \|p\|_1$

n

$n$

p

$p$

‖ q ‖_{1} \leq 1

$\|q\|_1 \leq 1$

q

$q$

p

$p$

‖ \cdot ‖_{1}

$\|\cdot\|_1$ denota a soma do valor abs dos coeficientes.

arnab

‖ p ‖_{1} \geq ‖ p ‖_{s u p}^{D_{1}}

$\|p\|_1 \geq \|p\|_{sup}^{D_1}$

D_{1}

$D_1$

p (0) - ‖ p ‖_{s u p}^{D_{1}}

$p(0) - \|p\|_{sup}^{D_1}$

p

$p$

1

$1$

D_{1}

$D_1$ . Fazendo uma transformação de coordenadas, nos encontramos no cenário do teorema dos Três Círculos: uma função holomórfica é delimitada em pontos em dois círculos concêntricos, delimitando a função em qualquer círculo de raio intermediário.

arnab

‖ p ‖_{s u p}^{D_{1}} \geq | p (0) |^{Ω (1)}

$\|p\|_{sup}^{D_1} \geq |p(0)|^{\Omega(1)}$

p

$p$

1

$1$

D_{1}

$D_1$

5

$\ell_p$ $0 < p < 2$

Daniel M. Kane, Jelani Nelson, David P. Woodruff. Sobre a complexidade exata do espaço de esboçar e transmitir pequenas normas. SODA 2010.

Você pode escrever uma prova que não mencione explicitamente a análise complexa (consulte o primeiro marcador na seção "notas" desse documento na minha página da web), mas mesmo essa prova tem análises complexas à espreita.

Jelani Nelson
fonte

4

Há uso de números e análises complexos em um artigo recente de Naor, Regev e Vidick, produzindo resultados em algoritmos de aproximação para problemas de otimização de NP-hard: http://arxiv.org/abs/1210.7656

Clemente C.
fonte

Outro artigo que utiliza raízes aleatórias da unidade é Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald e He Sun. Contando subgrafos arbitrários em fluxos de dados. ICALP 2012.

Jelani Nelson

3

$n + O(n/\sqrt{k})$ $k$ $n \times n$ $n!/n^n$ Laurent e Schrijver no MAA Monthly). Deixar a linha real para o plano complexo parece essencial para a prova de Gurvits e simplifica bastante as coisas.

Sasho Nikolov
fonte

0

$z \leftarrow z^2 + c$

[1] Inacessibilidade e indecidibilidade em sistemas de computação, geometria e dinâmica Asaki Saito, Kunihiko Kaneko

[2] Uma teoria da computação e complexidade sobre os números reais Lenore Blum, 1990

vzn
fonte

0

$\mathbb{C}$

Reb.Cabin
fonte

Análise complexa em ciência da computação teórica

Respostas: