Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was wondering what papers I should read to understand this question

A unexpected connection to other areas of mathematics such as algebraic geometry or higher cohomology. Perhaps even an area of mathematics not yet developed. Perhaps someone will develop a whole new direction for mathematics in order to handle the P versus NP question. -From Fortnow 2002

Another phrasing of the question would be "What papers should I read to create a connection from computational complexity to algebraic geometry / topology?"

I have looked at Geometric Complexity Theory already . Also papers in Topological Quantum Computation which I have read enough papers that I am already familiar with the field. Am I missing anything?

share|cite|improve this question
May I suggest a change to the title? Something like "Papers on relation between computational Complexity and algebraic geometry/topology". – Kaveh Aug 24 '11 at 21:39
Could you elaborate your question a bit? I would think everyone would miss something from that line if that line is true since he is talking about "unknowns". I think professor Suresh's answer below on lower bounds is a good reference. – v s Aug 25 '11 at 7:25
You may also want to look into this related question:… – Martin Schwarz Aug 25 '11 at 7:37
I also found this paper – Joshua Herman Aug 26 '11 at 11:03
up vote 13 down vote accepted

As background, you should definitely study Ben-Or's work on lower bounds, as well as Mulmuley's P vs NC paper.

share|cite|improve this answer
share|cite|improve this answer
Is this an explicit example of etale cohomology? – Joshua Herman Aug 25 '11 at 13:25
Please refer here. – v s Aug 25 '11 at 16:35
The work of Sudan and Guruswami is mostly devoted to list decoding (which, well, concerns AG codes as well) — topic that raised at the end of 90-s and was heavily developed at 2000-s. The algebraic geometry method appeared at 80-s in papers by Goppa, and was developed by Tsfasman and Vladutc and many others at 90-s. Personally I would suggest the paper: Hoholdt, van Lint, Pellikaan, Algebraic geometry codes, 1998. – Artem Pelenitsyn Sep 6 '11 at 19:33
As for computational AG I would suggest books by Cox—Little—O'Shea and Schenck, but this topic is a bit irrelevant to the “connection from computational complexity to algebraic geometry” which was requested by Joshua. – Artem Pelenitsyn Sep 6 '11 at 19:37

In Slide 26, Martin Escardo provides an algorithm that might give you what you're looking for:

  1. Go the library.
  2. Pick a book on topology.
  3. Pick a theorem.
  4. Apply the dictionary.
  5. Get a theorem in computation.

See also this paper

share|cite|improve this answer
The dictionary being a correspondence between terms in topology (like open set) and computability (like semi-decidable set). – Mitch Nov 16 '15 at 23:14
Thanks for the reference I downloaded the PDF. – Joshua Herman Nov 17 '15 at 3:27
maybe this should be the accepted answer – Nikos M. Dec 11 '15 at 19:44
@NikosM. I would be torn with the first answer and this one and the accepted answer has been accepted for awhile so I rather not change it. If there was a merged answer with everything maybe but then this question would probably become a community wiki. – Joshua Herman Dec 12 '15 at 1:11
@JoshuaHerman, sure i understand, although myself have sometimes changed the accepted answer as my knowledge updated and another answer more to the point of the question appeared. Anyway, about the topic, you will find out that there are many more analogies with other areas of mathematics as well (i,e not only between topology-complexity) For example, an area which has this potential (and was inspired by topology) is category theory – Nikos M. Dec 12 '15 at 11:05

Your Answer


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.