Titlebook: STACS 98; 15th Annual Symposiu Michel Morvan,Christoph Meinel,Daniel Krob Conference proceedings 1998 Springer-Verlag Berlin Heidelberg 199

吞下

Attractors of ,-dimensional Linear Cellular Automata,er we consider non-surjective cellular automata. We prove that, after a transient phase of length at most [log., .], the evolution of a linear non-surjective cellular automata . takes place completely within a subspace ... This result suggests that we can get valuable information on the long term be

争议的苹果

FLASK

In-Situ

A generalization of resource-bounded measure, with an application (Extended abstract), martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudo-random number generators exist, then betting games are equivalent to martingales, for measure on E and EXP. However, we construct betting games that succeed on certain cla

Pander

The complexity of modular graph automorphism,raph automorphism problems. These are the decision problems Mod.GA which consist, for each . > 1, of deciding whether the number of automorphisms of a graph is divisible by k. The Mod.GA problems all turn out to be intermediate in difficulty between Graph Automorphism and Graph Isomorphism. We defin

戏法

conquer

,On the structure of valiant’s complexity classes, this theory in the spirit of structural complexity and obtain analogues of well-known results by Baker, Gill, and Solovay [1], Ladner [18], and Schöning [23,24]..We show that if Valiant‘s hypothesis is true, then there is a .-definable family, which is neither .-computable nor VNP-complete. More ge

分期付款

On disguised double horn functions and extensions,ns. Furthermore, polynomial time algorithms for the recognition of a function in ... from Horn formulas and other classes of formulas are provided, while the problem is intractable in general. We also present an algorithm for the extension problem which, properly implemented, runs in linear time.

FISC

掺假

,On the structure of valiant’s complexity classes, family of polynomials which is neither VNP-complete nor .-computable, provided the polynomial hierarchy does not collapse..We define relativized complexity classes VP. and VNP. and construct complete families in these classes. Moreover, we prove that there is a .-family . satisfying VP. = VNP..