In order to study circuit complexity classes within NC 1 in a uniform setting, we need a
uniformity condition which is more restrictive than those in common use. Two such …

This book is a revised version of my Doctoral Dissertation, which was completed at the
Massachusetts Institute of Technology in November, 1988. The main purpose of the work …

A program correctness checker is an algorithm for checking the output of a computation.
That is, given a program and an instance on which the program is run, the checker certifies …

We give algorithms for the computation of the $ d $-th digit of certain transcendental
numbers in various bases. These algorithms can be easily implemented (multiple precision …

The birth of the theory of computational complexity can be set in the early 1960s when the
first users of electronic computers started to pay increasing attention to the performances of …

This handbook provides an up-to-date compendium of fundamental computer science
topics, techniques, and applications. Along with updating and revising many of the existing …

The paper considers two decision problems on hypergraphs, hypergraph saturation and
recognition of the transversal hypergraph, and discusses their significance for several …

Publisher Summary This chapter discusses the concepts needed for defining the complexity
classes. A complexity class is a set of problems of related resource-based complexity. A …

A complete treatment of fundamentals and recent advances in complexity theory Complexity
theory studies the inherent difficulties of solving algorithmic problems by digital computers …

This book presents a nearly complete classification of various restricted classes of
computational problems called Boolean constraint satisfaction problems. Roughly, these are …