Name: Anonymous 2011-04-18 12:24
Galois theory associates to each polynomial a chain of groups, if each group happens to be cyclic then the polynomial is solvable by radicals.
There is also a "differential" Galois theory which associates chains of groups to differential equations, solvability by radicals is replaced by existence of a solution by exponentials and logarithms.
I have invented a new theory of computation called "Algorithmic" Galois theory. It associates to (a restricted syntax of) program specifications a lattice of groups. I apply standard results from Model theory to show that the lack of certain "shapes" inside the graph of groups is exactly equivalent to the existence of a polynomial time algorithm implementing the program specification.
A rather difficult and long calculation of the graph for the subset sum (NP complete) shows that its graph of groups contains certain symbols obstructing polytime algorithms form existing. This results the P=NP problem.
I have also been able to re-prove the "Primes in P" result as an example of my theory. Although algorithms cannot be "extracted" from my theory, it is useful in guiding algorithm design (I have developed several apparently new for basic problems in CS - one of which, matrix multiplication, beats the current best known algorithm).
There is also a "differential" Galois theory which associates chains of groups to differential equations, solvability by radicals is replaced by existence of a solution by exponentials and logarithms.
I have invented a new theory of computation called "Algorithmic" Galois theory. It associates to (a restricted syntax of) program specifications a lattice of groups. I apply standard results from Model theory to show that the lack of certain "shapes" inside the graph of groups is exactly equivalent to the existence of a polynomial time algorithm implementing the program specification.
A rather difficult and long calculation of the graph for the subset sum (NP complete) shows that its graph of groups contains certain symbols obstructing polytime algorithms form existing. This results the P=NP problem.
I have also been able to re-prove the "Primes in P" result as an example of my theory. Although algorithms cannot be "extracted" from my theory, it is useful in guiding algorithm design (I have developed several apparently new for basic problems in CS - one of which, matrix multiplication, beats the current best known algorithm).