Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: applications of algebraic topology

Jules Hedges (Apr 06 2020 at 20:43):

So, anyone want to prove $P \neq NP$ by showing they have different cohomology groups?

Matteo Capucci (he/him) (Apr 06 2020 at 20:57):

What if... it turns out you need to compute the homotopy of spheres to distinguish

Reed Mullanix (Apr 06 2020 at 21:44):

On a somewhat unrelated note, the linked paper has a really lovely introduction

Morgan Rogers (he/him) (Apr 07 2020 at 09:19):

Jules Hedges said:

So, anyone want to prove $P \neq NP$ by showing they have different cohomology groups?

This might have been a little tongue in cheek, but I would love to do this! A geometric proof that $P \neq NP$ would be delightful!

John Baez (Apr 07 2020 at 17:23):

Maybe any proof would be delightful.

Amar Hadzihasanovic (Apr 07 2020 at 17:55):

What are examples of “hard” separation results that have been first proved with homology/cohomology?

It seems that in basic AT courses, homology is often motivated by examples of this sort (“we can easily prove that spheres of different dimension are never homotopy-equivalent!”), but then the focus shifts on “understanding the structure of specific spaces”.

Amar Hadzihasanovic (Apr 07 2020 at 17:56):

Are there famous cases of “we didn't know if $X$ and $Y$ are the same or not, and we proved that they are not by showing that they have different homology/cohomology”?

Sam Tenka (Apr 07 2020 at 18:14):

Amar Hadzihasanovic said:

What are examples of “hard” separation results that have been first proved with homology/cohomology?

It seems that in basic AT courses, homology is often motivated by examples of this sort (“we can easily prove that spheres of different dimension are never homotopy-equivalent!”), but then the focus shifts on “understanding the structure of specific spaces”.

Perhaps more finegrained than you were hoping for, but Ben-Or showed some lower bounds for problems such as counting the number of distinct elements in a list ("Lower bounds for algebraic computation trees", 1983). The idea is to an algebraic decision tree model of computation and upper bound the number of connected components that can arise from a given number of steps.

John Baez (Apr 07 2020 at 18:16):

The "hard" questions about distinguishing spaces tend to be solved not using homology or cohomology groups (which count as "easy"), but with cohomology rings, fancier cohomology operations like Steenrod operations, homotopy groups, etc.

John Baez (Apr 07 2020 at 18:19):

For example, suppose you're trying to show $\mathbb{C}P^2$ is not homotopy equivalent to $S^2 \vee S^4$.

John Baez (Apr 07 2020 at 18:20):

Both of them have the same homology and cohomology groups, but they have different cohomology rings.

This doesn't count as "hard" - it's a textbook exercise - but it might be hard without using the ring structure on cohomology.

John Baez (Apr 07 2020 at 18:23):

Btw, if you want to see homology used to rule out the possibility of a confluent and terminating rewriting system with finitely many rewrite rules, try the work of Craig Squier.

Amar Hadzihasanovic (Apr 07 2020 at 18:26):

Oh I'm a big fan of Squier's work :) and I know lots of examples of (co)homology used to find interesting combinatorial bounds, obstructions etc.

Just not many cases where the question is strictly “are these two things 'the same' (up to some notion of equivalence)?”

John Baez (Apr 07 2020 at 18:29):

Topologists will happily give you piles of examples of spaces that match in a bunch of ways but differ in some other way.

John Baez (Apr 07 2020 at 18:30):

It's possible that most of these are examples cooked up to illustrate the power of their techniques, rather than spaces people had already been eager to distinguish. :upside_down:

Jules Hedges (Apr 07 2020 at 18:49):

Wow, I never heard of using algebraic topology in combinatorics like that..... if only I had some time, that would motivate me to learn something

Amar Hadzihasanovic (Apr 07 2020 at 18:54):

I guess looking at the “Homological theory of functions” paper linked above made me wonder:

I can also think of many “separation” problems (including the Squier ones, rephrased in a certain way) that are proved in this way: “every object $x$ of a class $C$ has a property $P$ which is really a property of some (co)homology of $x$; here's an object $y$ of $D$ which does not have $P$; therefore $C \neq D$”.

My naive guess would have been that an approach to complexity separation results would have been in this spirit, defining the (co)homology of functions in some complexity class.

Instead that paper seems to associate a combinatorial complex (and then its singular homology) to the entire complexity class...

Amar Hadzihasanovic (Apr 07 2020 at 18:59):

I don't know, I'd be astonished if this single space turned out to contain interesting and computable information about something which seems really complicated in all the interesting cases (eg, P or NP) :)