Complexity theory is one of the spin-offs of computer science. So far it is a chapter with some solved and plenty of unsolved problems. One exception is the theory of cost of computations where additions and subtractions are considered to cost nothing and the total cost is measured in terms of the number of multiplications and divisions necessary to achieve the algorithm. The essential tool is very simple: abstract linear algebra, but the results are far from trivial. They are the subject of the second section of this chapter, the first one contains some preliminary generalities on rings generated by indeterminates.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Algebraic complexity theory
- Springer US
- Chapter 6
ec4u, Neuer Inhalt/© ITandMEDIA