The difference and truth-table hierarchies for NP
The helping hierarchy
Schöning [14] introduced a notion of helping and suggested the study of the class of the languages that can be helped by oracles in a given class . Later, Ko [12], in order to study the connections between helping and “witness searching”, introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call which contains all the self-helping classes. We introduce the Helping hierarchy whose levels are...
The Helping Hierarchy
Schöning [14] introduced a notion of helping and suggested the study of the class of the languages that can be helped by oracles in a given class . Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...
The laterality problem for non-erasing Turing machines on is completely solved
The role of rudimentary relations in complexity theory
The second machine class 2, an encyclopedic view on the parallel computation thesis
Threshold circuits for iterated matrix product and powering
Threshold Circuits for Iterated Matrix Product and Powering
The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension matrices with integer or rational entries is studied. We call these two problems and , respectively, for short. We prove that: (i) For , does not belong to , unless .newline (ii) For stochastic matrices : belongs to while, for , does not belong to , unless . (iii) For any k, belongs to .
Time and space complexity of reversible pebbling
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
Time and space complexity of reversible pebbling
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
Topological views on computational complexity.
Traces of term-automatic graphs
In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...
Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]
Two-way multihead automata over a one-letter alphabet