Martin Ziegler
Real Analytic Machines and Degrees.
Thu, 06/03/2010 - 15:01 — SomNambulAuthors: Martin Ziegler, Tobias Gärtner
Subjects: Logic in Computer Science
AbstractWe study and compare in two degree-theoretic ways (iterated Halting oracles
analogous to Kleene's arithmetical hierarchy and the Borel hierarchy of
descriptive set theory) the capabilities and limitations of three models of
analytic computation: BSS machines (aka real-RAM) and strongly/weakly analytic
machines as introduced by Hotz et. al. (1995).Expressiveness and Computational Complexity of Geometric Quantum Logic.
Tue, 04/13/2010 - 15:02 — SomNambulAuthors: Martin Ziegler, Christian Herrmann
Subjects: Logic
AbstractQuantum logic generalizes, and in dimension one coincides with, Boolean
logic. We show that the satisfiability problem of quantum logic formulas is
NP-complete in dimension two as well. For higher higher-dimensional spaces R^d
and C^d with d>2 fixed, we establish quantum satisfiability to be polynomial
time equivalent to the real feasibility of a multivariate quartic polynomial
equation: a problem well-known complete for the counterpart of NP in the
Blum-Shub-Smale model of computation lying (probably strictly) between
classical NP and PSPACE.Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability.
Thu, 09/03/2009 - 17:38 — SomNambulAuthors: Martin Ziegler
Subjects: Computational Complexity
AbstractIt is folklore particularly in numerical and computer sciences that, instead
of solving some general problem f:A->B, additional structural information about
the input x in A (that is any kind of promise that x belongs to a certain
subset A' of A) should be taken advantage of. Some examples from real number
computation show that such discrete advice can even make the difference between
computability and uncomputability.
User login
