Computer Science – Computational Complexity
Scientific paper
2006-12-25
Computer Science
Computational Complexity
46 pages
Scientific paper
In part I we reduced the arithmetic (characteristic zero) version of the P \not \subseteq NP conjecture to the problem of showing that a variety associated with the complexity class NP cannot be embedded in the variety associated the complexity class P. We call these class varieties. In this paper, this approach is developed further, reducing the nonexistence problems, such as the P vs. NP and related lower bound problems, to existence problems: specifically to proving existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel-Weil theorem to a class of orbit closures, which include class varieties. The recond result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class NC. These results indicate that the fundamental lower bound problems in complexity theory are intimately linked with explicit construction problems in algebraic geometry and representation theory.
Mulmuley Ketan D.
Sohoni Milind
No associations
LandOfFree
Geometric Complexity Theory II: Towards explicit obstructions for embeddings among class varieties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Geometric Complexity Theory II: Towards explicit obstructions for embeddings among class varieties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometric Complexity Theory II: Towards explicit obstructions for embeddings among class varieties will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-122974