Recently there has been a great deal of literature on category theory and computational complexity. On the other hand I am currently unsatisfied with geometric complexity theory and I think knot theory can be used to counteract this. I believe it can be reformulated into a more topological version that could cut down on the amount of computations.
See http://arxiv.org/abs/0908.1936
Therefore we try to formulate a new antithesis to turnings thesis.
The power of a oracle in $ALL$ deciding the entropy of a given language.
strategies
Also, Lance Fortnow lamented that Geometric Complexity theory is too complicated and would take one month to study to do useful results. Therefore, most of this post will try to simplify the thesis so that it wouldn't take a month for you understand geometric complexity theory. In effect this is an attempt to rewrite geometric complexity theory to be much simpler but still you can use the same tools. The time horizons are unreasonable for someone to learn so can we make shortcuts? To that end I try to employ shortcuts and attempt to attack the class of all languages. But first you must learn my approach.
Therefore, I wish to ask the question "What do you think would be a good way to speed up Mulmuley's program?" Therefore someone must bite the bullet and create tools to counteract the complexity of his arguments. To try this I wish to use ideas from category theory
I have a few ideas.
- Use ideas from category theory to simplify arguments. (Monoidal categories) [1]
- Reformulate the program to tackle problems in topological computation (much research on topological quantum computation and even classical one) and show correspondance to representation of groups to the TemperleyÐLieb algebra [1]
- Show theories in quantum computation are equivalent
- Mix and match the above techniques. [1] [2]
My attempt to mix and match the above techniques is as follows. I wish to change the perspective of complexity theory to a topological one. Classes, and algorithms become probabilistic state spaces. A running of an algorithm becomes a path inside of one or more probabilistic state space. Algorithms eventually are bound inside a probabilistic state space such as a class. The reason for this probabilistic state space is that I am using tools from algebraic geometry / cohomology to create an new tools to attack complexity theory.
We attempt to respond to what is unreasonable in complexity theory and create an oracle that can answer questions about the reasonable and unreasonable.
My idea to mix and match the above techniques is as follows. First I try to take the idea of an oracle in $ALL$ [3] and what useful thing that oracle could tell me. The oracle in $ALL$ could be used. I use an oracle in $ALL$ to ask the question what is the Kolmogorov complexity of each complexity class. Then I assign a probability space to each complexity class which I define as the total state space of that complexity class. Any problems in that class will be bounded within each complexity class.
Therefore a central thesis would be as follows. Given any complexity class an element of that complexity class will be bounded by resource complexity and it will only exist within that probabilistic state space of that complexity class. To formulate this in the words of geometric complexity theory this would be a flip
To formulate it in a new concept we take the idea of a flip and abstract it into three operations. There are flips from every infeasable and feasible complexity class.
**Refrences**
[1] http://math.ucr.edu/home/baez/rosetta.pdf
[2] http://people.cs.uchicago.edu/~fortnow/papers/history.pdf
[3] http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#all
0 comments:
Post a Comment