We review ten years of work in modeling the computation of analog-digital systems that express the physical reality in the limit, an outcome of our involvement in the conferences UC (Unconventional computation) and UC...
详细信息
We review ten years of work in modeling the computation of analog-digital systems that express the physical reality in the limit, an outcome of our involvement in the conferences UC (Unconventional computation) and UCNC (Unconventional computation and Natural computation). Computers are connected with sensors that measure physical quantities such as distance, electric current, mass, pressure, temperature, etc, interfering in the environment as experimenters. In this paper, we consider the experimenter (e.g. the experimental physicist) as a Turing machine - the digital component - and the experiment of measurement - the analog component - as an oracle to the Turing machine. The algorithm running in the machine abstracts the method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. The interaction between the machine and the sensors is mediated by a protocol, that specifies the experimental error, and a schedule, that determines its running time. We then overview the computational complexity classes related to diverse protocols between the digital and the analogue parts of the digital-analogue machine. (C) 2022 Elsevier B.V. All rights reserved.
Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers...
详细信息
Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membership in the set of algebraic numbers of degree d + 1. We add a number of further results on relative computability of these sets and their unions. Then we show that the halting problem for BSS-computation is not decidable below any countable oracle set, and give a more specific condition, related to the cardinalities of the sets, necessary for relative BSS-computability. Most of our results involve the technique of using as input a tuple of real numbers which is algebraically independent over both the parameters and the oracle of the machine.
The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f and g, with domain sizes N and M(N 1, where the domain sizes of ...
详细信息
The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f and g, with domain sizes N and M(N <= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. it can also be generalized to find a claw of k functions for any constant integer k > 1, where the domain sizes of the functions may be different. (C) 2009 Elsevier B.V. All rights reserved.
We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear optimization oracle. We provide a polynomial-time algorithm that determines an r-best solu...
详细信息
ISBN:
(纸本)9783642021572
We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant depending on certain Frobenius numbers of the weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time even in a very special case of the problem.
作者：
Tani, SeiichiroJST
SORST ERATO Quantum Computata & Informat Project Tokyo Japan
for any constant integer k > 1, where the domains of the functions may have different *** claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography....
详细信息
ISBN:
(纸本)9783540744559
for any constant integer k > 1, where the domains of the functions may have different *** claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N <= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This paper describes a quantum-walk-based algorithm that solves this problem;it improves the previous upper bounds. Our algorithm can be generalized to find a claw of k functions for any constant integer k > 1, where the domains of the functions may have different size.
Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteri...
详细信息
Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish. (C) 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
暂无评论