FoCM 2014 conference
Workshop A6 - Real Number Complexity
December 11, 18:30 ~ 19:00 - Room C11
Towards a Broader View of Theory of Computing -- Part 1
Narendra Karmarkar
Indian Institute of Technology, Bombay, India - narendrakarmarkar@yahoo.com
Beginning with the projectively invariant method for linear programming, interior point methods have led to powerful algorithms for many difficult computing problems, in combinatorial optimization, logic, number theory and non-convex optimization. Algorithms for convex optimization benefitted from many pre-established ideas from classical mathematics, but non-convex problems require new concepts. This three part series outlines some of these concepts-- computational models based on the concept of the continuum, algorithms invariant w.r.t. projective , bi-rational , and bi-holomorphic transformations on co-ordinate representation, extended proof systems for more efficient certificates of optimality, extensions of Grassmann’s extension theory, efficient evaluation methods for the effect of exponential number of constraints , theory of connected sets based on graded connectivity, theory of curved spaces adapted to the problem data, and concept of “ relatively” algebraic sets in curved space.
Models of Computation provide mathematical abstractions of basic data objects and operations on them available as building blocks. This effectively decouples design of algorithms for complex tasks from lower level details of how the underlying hardware implements the building blocks. The Turing machine model uses strings of 0’s and 1’s and finite state machines. Careful study of the work of early pioneers – Turing,Von Neumann and Godel – shows that they were acutely aware of the limitations of this model for comprehensive understanding of the fundamental aspects of computation. BSS model uses real or complex numbers as data objects and algebraic operations ( including comparisons in real case ). This is more natural for many algorithms in numerical analysis. Various computing models can be organized in a similar way as Cantor had organized infinite sets—by cardinal number of the set of all possible machines and data objects in the model. Staying within the same cardinal number, a more powerful approach is to use further extension, e.g real analytic functions or algebraic closure of meromorphic functions over suitable domains. Operations include algebraic as well as analytic operations. i.e. integration and differentiation are regarded as binary operations. ( specification of the contour of integration is one of the input operands ) All such models are collectively referred to as continuum computing. Time permitting, more topics from the list above will be covered in the first part.