Главная

Martin Ziegler

  1. Real Analytic Machines and Degrees.

    Чт, 06/03/2010 - 15:01 — SomNambul
    Authors: Martin Ziegler, Tobias Gärtner
    Subjects: Logic in Computer Science
    Abstract

    We 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).

  2. Expressiveness and Computational Complexity of Geometric Quantum Logic.

    Втр, 04/13/2010 - 15:02 — SomNambul
    Authors: Martin Ziegler, Christian Herrmann
    Subjects: Logic
    Abstract

    Quantum 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.

  3. Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability.

    Чт, 09/03/2009 - 17:38 — SomNambul
    Authors: Martin Ziegler
    Subjects: Computational Complexity
    Abstract

    It 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.

Math-arch

RSS-материал