On Measures of Space over Real and Complex Numbers

Authors: Om Prakash and B. V. Raghavendra Rao

Department of Computer Science

IIT Madras

Presented at 26^th International Computing and Combinatorics Conference 2020.

Brief Outline

1

Brief History

2

Motivation

3

Introduction

4

5

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Brief Outline

1

Brief History

2

Motivation

3

Introduction

4

5

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Brief History

• In 1930’s work of Turing, Gödel, Church and others lead to Classical theory of Computation over natural numbers.

• Rabin, Steele-Yao, Ben-Or proposed decision and computation tree models—less general purpose

• Formal Development of theory of real RAM– BSS model of computation over a ring—particular reals.

Brief Outline

✔

Brief History

2

Motivation

3

Introduction

4

5

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Motivation

Why another Model of Computation?

• Computational aspects of numerical algorithms e.g. Newton-Raphson method

• Algebraic approach to the study of computation, rather than classical approach based on logic.

• Bringing the theory of computation in the realms of analysis, topology and geometry.

• ¹In 1989, L. Blum, M. Shub and S. Smale proposed new model of computation (BSS model).

¹Lenore Blum, Mike Shub and Steve Smale. “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines”. In Bulletin of AMS: 1989 pp 1-46

Brief Outline

✔✔

Brief History

✔

Motivation

3

Introduction

4

5

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Finite State Machine (Newton Machine)

Yes

No

No

Yes

Newton Machine

• Machine can be in any one of the four state Input, Compute, Branch or Output

• Machine parameter (epsilon)

Source: Blum, Shub and Smale

BSS Machine as Real TM

A BSS machine M with machine constants is given by a finite set of instructions labelled by

The instructions M can perform are of four types:

• Computation: where or where are address of read registers, go to next instruction

• Branch: if go to instruction else go to next instruction

• Read:

• Write:

BSS Machine as Real Turing Machine

read

read

write

Finite set of Instructions

M/C constants

​

ꓕ

Brief Outline

✔

Brief History

✔

Motivation

✔

Introduction

4

5

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Structural Complexity

²L. Blum, M. Shub and S. Smale established various structural complexity results:

• Over captures the classical complexity.

• Based on unit cost, Real counterparts , .

• Notion of polytime reduction.

²Lenore Blum, Mike Shub and Steve Smale. “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines”. In Bulletin of AMS: 1989 pp 1-46

​

Structural Complexity

³Felipe Cucker, In Journal of Complexity (1992) pp 230-238

Brief Outline

✔

Brief History

✔

Motivation

✔

Introduction

✔

5

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Space Measure

What are the suitable candidates for space measure in the BSS model?

• Unit Space measure seems to be the natural candidate.

• ⁴Michaux showed that the unit cost measure is not suitable.

Theorem:

Let be a real language accepted by machine M in time

then can be decided by machine M’ in constant unit space.

​

⁴Christian Michaux. “Une remarque à propos des machines sur introduites par Blum, Shub et Smale”. In Comp. Rend de l’ Acad. Des Sci. de Paris 1989 pp 435-437

Space Measure

• Following above, focus shifted on circuit based parallel complexity classes

like

• ⁵F. Cucker and D. Grigoriev obtained following result:

Theorem:

​

​

⁵Felipe Cucker and Dima Grigoriev. “On the power of real Turing Machines over Binary inputs”. In SIAM Journal of Computing 1997 pp. 243-254

Brief Outline

✔

Brief History

✔

Motivation

✔

Introduction

✔

✔

6

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Weak Cost

• ⁶Koiran introduced notion of weak cost to charge for repeated squaring.

Definition:

If the current instruction is compute and the current transition is from

that consists of computing a rational function

. Then the weak cost of the transition is

Otherwise 1

⁶Pascal Koiran. “A weak version of the Blum, Shub, and Smale Model”. In JCSS 1997 pp 177-189

Weak Cost

Weak Space

• Motivated by the weak cost, ⁷Naurois introduced weak space, a simplified definition is:

Definition:

The weak space of the rational (polynomial for division free computation)

function f is the sum of length of binary encoding of g and h in the explicit sparse form.

• Weak Space, overcame unit space obstacle.

Theorem:

There is a that cannot be computed by any BSS machine running in weak space for any constant

⁷Paulin Jocobè de Naurois. “A Measure of Space for Computing over the Reals”. In CiE 2006 pp 231-240

Weak Space

Theorem:

​

• ⁸Joglekar et. al showed limitation of weak space. In particular,

Theorem:

​

• Finding suitable notion of space still remains a challenging task.

⁸Pushkar Joglekar, B. V. Raghavendra Rao and Sidhartha Sivakumar “On Weak Space Complexity over Complex Numbers”. In FCT 2017 pp 87

SPACETIME

• What about simultaneous bound on time and space⁹?

Theorem:

​

​

Theorem:

​

⁹Felipe Cucker. “On the Complexity of Quantifier Elimination: the Structural Approach”. In Comput. J. 1993 pp 400-408

Brief Outline

✔

Brief History

✔

Motivation

✔

Introduction

✔

✔

✔

7

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Circuit Size

• What about size of arithmetic circuit implicit in computation?

Observation:

​

​

Theorem:

For ,

​

Circuit Size as Space Measure

C

Arithmetic Circuit

M/C Constants

Circuit Size

Theorem:

Over the field of Complex numbers,

​

Proof Idea:

Circuit Size

BSS m/c M with algebraic constants over and transcendental constants

Initial configuration of TM M’ consists of inputs

Current op of M

Build the arithmetic circuit inductively.

size is

larger

Search for a smaller circuit and verify using PIT

Perform identity test modulo the univariate minimal polynomials

Yes

No

Arithmetic

Test

Brief Outline

✔

Brief History

✔

Motivation

✔

Introduction

✔

✔

✔

✔

8

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

New Branching Program

• BSS model can be seen as a generalization of Valiant’s¹⁰ algebraic model of computation.

• ABPs play an important role in Valiant’s theory.

• Can we have a similar concept of ABPs in the context of BSS model of computation.

¹⁰L. G. Valiant. “Completeness Classes in algebra”. In STOC 1979 pp 249-261

ABPs with Select Nodes

ABPs with Select Nodes

New Branching Program

• The complexity classes based on ABP are:

Definition:

​

​

​

​

• Similarly,

New Branching Program

Theorem:

​

​

• Can we obtain real analogue of Ben-Or and Cleve¹¹ result?

¹¹Michael Ben-Or and Richard Cleve. “Computing algebraic formulas using a constant number of registers”. In SIAM Journal on Computing 1992 pp 54-58

Algebraic Formula

Algebraic Formula

Algebraic Formula

Theorem:

Let be a set accepted by a family of algebraic formula such that is of polynomial size, depth and has atmost test gates. Then can be accepted by a family of constant-width polynomial-size algebraic branching programs with select nodes.

​

Algebraic Formula

• Do we have depth-reduction¹² as in the classical case?

Lemma:

Let be a family of algebraic formulas, of size and containing at most comparison gates accepting a set . Then for every , there is an algebraic formula of size and depth such that the family accepts . Moreover, if the family is log-space uniform, then so is .

¹²Richard P. Brent. “The Parallel Evaluation of General Arithmetic Expressions”. In JACM 1974 pp 201-206

Brief Outline

✔

Brief History

✔

Motivation

✔

Introduction

✔

✔

✔

✔

✔

9

Weak Cost

Circuit Size as Space Measure

ABPs and Formulas

Summary

Previous Work

Basic Notions

Summary

• Explored feasibility of circuit size and simultaneous unit space and unit time as measure of space.

• Real analogue of Ben-Or and Cleve’s result is worth exploring.

Thank You