## Completeness and Reduction in Algebraic Complexity TheoryOne of the most important and successful theories in computational complex ity is that of NP-completeness. This discrete theory is based on the Turing machine model and achieves a classification of discrete computational prob lems according to their algorithmic difficulty. Turing machines formalize al gorithms which operate on finite strings of symbols over a finite alphabet. By contrast, in algebraic models of computation, the basic computational step is an arithmetic operation (or comparison) of elements of a fixed field, for in stance of real numbers. Hereby one assumes exact arithmetic. In 1989, Blum, Shub, and Smale [12] combined existing algebraic models of computation with the concept of uniformity and developed a theory of NP-completeness over the reals (BSS-model). Their paper created a renewed interest in the field of algebraic complexity and initiated new research directions. The ultimate goal of the BSS-model (and its future extensions) is to unite classical dis crete complexity theory with numerical analysis and thus to provide a deeper foundation of scientific computation (cf. [11, 101]). Already ten years before the BSS-paper, Valiant [107, 110] had proposed an analogue of the theory of NP-completeness in an entirely algebraic frame work, in connection with his famous hardness result for the permanent [108]. While the part of his theory based on the Turing approach (#P-completeness) is now standard and well-known among the theoretical computer science com munity, his algebraic completeness result for the permanents received much less attention. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

I | 1 |

II | 3 |

III | 4 |

IV | 6 |

V | 11 |

VII | 16 |

IX | 19 |

X | 21 |

XXXII | 76 |

XXXIII | 81 |

XXXIV | 82 |

XXXV | 85 |

XXXVI | 89 |

XXXVII | 92 |

XXXVIII | 96 |

XXXIX | 105 |

### Other editions - View all

### Common terms and phrases

algebraic algorithm arithmetic operations assume Biirgisser bijection Boolean circuits bounded BP(VNPfc BSS-model Chap claim class VP Cn(h coefficients Comp complete graph complexity class compute constants contained Corollary corresponding countable cr-limit sets Cut9 cycle covers cycle format decision problem defined diagonal digraph disjoint union Dn(h edge weighted graph evaluate finite field fn(x formula Gelfand-Tsetlin basis graph G graph property Hamilton cycle Hence homogeneous immanants implies indeterminates induction integer polynomial irreducible k[Xi Lemma Let f linear matrix Moreover multiplication natural numbers nonscalar nonuniform number of variables obtain p-bounded function p-computable families p-definable families p-degrees p-family p-projection P/poly partition permanent planar planar graphs polynomial f polynomial hierarchy poset projection Prop prove representation result s-t-paths satisfying Sect sequence straight-line program string functions subgraph subsets Theorem theory Turing machine Valiant's hypothesis vector VNP-complete VNPh weighted graph

### References to this book

Computing and Combinatorics: 7th Annual International Conference, COCOON ... Jie Wang No preview available - 2001 |