Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to write a function that does the following:

Input:

  1. An integer $n$
  2. A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets "yes," and (b) if any set gets "yes" then all its subsets get "yes" too.
  3. An integer $k \le n$

Jointly, these two inputs define an abstract simplicial complex.

Output:

  1. The rank of the homology group $H_k$ of the simplicial complex.

I want a function that is polynomial in the value of $n$ (not the size of the bit representation of $n$) that solves this problem. Can this be done?

share|improve this question
    
This seems to suggest that it is possible to compute every Betti number, although I haven't thought very hard about its runtime yet. –  GMB Apr 27 '13 at 5:05
    
Turns out that algorithm is exponential in the worst-case. Hm. –  GMB Apr 27 '13 at 5:06

2 Answers 2

A counting argument suggests this is not true, as there are $2^{2^n}$ complexes , and in time $P(n)$ you cannot, in some sense, use all of the input.

For instance, to know the number of generators of the top dimensional homology, in the case where all maximal simplices are of cardinality $[n/2]$, you need to know how many maximal simplices there are, and it could be the cardinality of an arbitrary subset of a set of size ${n \choose {[n/2]}} \hskip3pt$. I don't see how to do that without brute force checking of all possibilities, whose number is exponential in $n$.

share|improve this answer
    
That's what I was afraid of, but I keep finding veiled references in the literature that suggest that it's possible and maybe has been done. I'm going to leave the question open in case someone has an idea for how to beat the brute force algorithm. –  GMB Apr 27 '13 at 4:45
    
Wait, the edit says $H_{n-1}$. Did you really mean that, or $H_{k-1}$ where $k$ is not equal to $n$ necessarily? There are only a polynomial number of possibilities for the simplices of cardinality $n-1$ and $n$, so ... –  zyx Apr 27 '13 at 4:47
    
Yes, sorry, I just threw that in. I really do mean $H_{n-1}$. I thought a general algorithm for $H_k$ would be cool, but for my specific application for this problem, I only need $H_{n-1}$. Figured I'd loosen my question a bit, since $H_k$ didn't seem promising. –  GMB Apr 27 '13 at 4:51
1  
I see. But then all you need to do is count the number of cardinality $n-1$ and $n$ subsets with $f=1$, which is polynomial time. –  zyx Apr 27 '13 at 5:23

Homology can be computed in polynomial time in the number of simplices -- this is just a Smith normal form computation -- but that is not the same thing as polynomial in $n.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.