16
$\begingroup$

computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra.

However, being a analysist, I wonder whether there are applications of analysis into this field, or maybe ideas inspired by analysis. All I know which slightly corresponds to this is the Fourier transform on Finite groups.

Can you help me?

Improve this question
$\endgroup$
7

7 Answers 7

Reset to default
18
$\begingroup$

Flajolet and Sedgewick published the book "Analytic Combinatorics" http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html. I don't know much about that topic, but people in the field use tools from complex analysis. So far, their applications seem more on analysis of algorithms, not on computational complexity, as far as I see.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Similar techniques (apparently) can be used to obtain asymptotic (expected) runtime results -- with constants. $\endgroup$
    – Raphael
    Jan 21, 2011 at 8:25
9
$\begingroup$

Markov Chain Monte Carlo algorithms are a useful tool for finding approximation algorithms. Some techniques for showing that these Markov chains mix are inspired by or come directly from analysis - for example see the chapter on estimating the volume of a convex body in Mark Jerrum's book on counting.

There are analytic approaches to Szemerédi's lemma, which has a cute application to combinatorial property testing. Szemerédi's Lemma for the Analyst has a randomized algorithm for finding a weakly regular partition of a graph; also see Graph Limits and Parameter Testing.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ A connection of Markov Chain Monte Carlo methods with analysis reminds me of the book by Montenegro and Tetali "Mathematical Aspects of Mixing Times in Markov Chains" dx.doi.org/10.1561/0400000003. $\endgroup$
    – Yoshio Okamoto
    Jan 21, 2011 at 0:44
8
$\begingroup$

Functional analysis is playing an increasingly important role in the theory of metric embeddings. While it's difficult to enumerate all aspects of the interaction, the major theme is the use of methods from functional analysis to understand how metrics embed into normed spaces. This latter problem comes up in the sparsest cut problem, which is an important graph optimization problem.

For more information, a good source is anything by Assaf Naor.

Improve this answer
$\endgroup$
7
$\begingroup$

Not about computational complexity, but interesting nonetheless

Some approaches to the semantics of infinite computation are based on metric spaces. Googling "metric space semantics" turns up plenty. One (oldish) reference on the topic is Control Flow Semantics by de Bakker and de Vink. Some recent work has been done by our very own Neel, namely Ultrametric Semantics for Reactive Programs. The area is very different from those described above, but concepts from analysis certainly find home here.

Improve this answer
$\endgroup$
6
$\begingroup$

The resource bounded measure theory developed by Jack Lutz is a great area for people who have background in analysis to work on. The original paper

Almost everywhere high nonuniform complexity, Jack H. Lutz, Journal of Computer and System Sciences, 1992.

generalize the notion of Lebesgue measure into complexity classes, and many following works can be found on the internet.

Intuitively, consider the $\mathsf{P}$ vs $\mathsf{NP}$ problem. If we can define (yes we can) a measure on complexity classes with respect to a large class, say $\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$, and prove that the measure of $\mathsf{P}$ is smaller than the measure of $\mathsf{NP}$, then $\mathsf{P} \neq \mathsf{NP}$. Moreover, we can prove statement like "almost all functions in $\mathsf{ESPACE}$ need $\Omega(2^n/n)$ gates", which extends Shannon bound to a restricted class $\mathsf{ESPACE}$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What is $E$ here? $TIME[2^{O(n)}]$? If so, then "almost all functions in $E$ need $\Omega(2^{n}/n)$ gates" is very far from known... $\endgroup$
    – Ryan Williams
    Jan 24, 2011 at 7:46
  • $\begingroup$ @Ryan: It should be $\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$. I'll fixed the answer, thank you Ryan! $\endgroup$
    – Hsien-Chih Chang 張顯之
    Jan 24, 2011 at 7:55
  • $\begingroup$ Is it possible that NP has a positive measure in ESPACE? I had believed that PSPACE (and therefore also NP) has measure zero in ESPACE. $\endgroup$
    – Tsuyoshi Ito
    Jan 29, 2011 at 21:04
  • $\begingroup$ @Tsuyoshi: I have to say that I don't know. At least there are no direct evidence that NP has positive measure or not. I'm curious about what made you believe that PSPACE has zero measure in ESPACE? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Jan 31, 2011 at 2:15
  • $\begingroup$ I thought so by analogy because I remembered that I have seen that “P has measure 0 in E.” After Googling, I found that the book chapter “The quantitative structure of exponential time” cites the article you cited for the result “P has measure 0 in E.” Unfortunately I have not understood this result (even what the statement exactly means), and I cannot be sure that it really implies “PSPACE has measure 0 in ESPACE” by analogy (or even that this statement makes any sense). $\endgroup$
    – Tsuyoshi Ito
    Jan 31, 2011 at 4:34
5
$\begingroup$

People who are working in different areas of computer science may benefit from various subfields of analysis.

To give you a concrete example, I'll describe my own case. I'm conducting research in foundations of cryptography. In this field (as well as in the computational complexity), there's a construct called the random oracle (see also this page). Its various properties are sometimes studied by exploiting tools from measure theory, which is a subfield of analysis. Such treatment can be found in this paper, as well as in several papers which cite it.

You can also take a look at Basics of Algebra and Analysis for Computer Science by Jean Gallier. It's a book in progress, and tells you what's new in the field.

Improve this answer
$\endgroup$
0
4
$\begingroup$

I believe the best connection between mathematical analysis and complexity theory is in the Blum et al's real computation model. It is still an open problem to separate NP_R from P_R, where the two classes are defined in the real computation model, in which every real number is an entity, and one regular operation (+,-,*,/) takes one step.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to cstheory, Bin Fu! I should say, though, that the Blum et al model is controversial, and many computable analysts prefer Type Two Effectivity, as the Blum et al model seems unrealistic. See this question for more discussion. $\endgroup$
    – Aaron Sterling
    Jan 25, 2011 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.