The Experts below are selected from a list of 3936 Experts worldwide ranked by ideXlab platform
Moritz Müller - One of the best experts on this subject based on the ideXlab platform.
-
Hard Instances of Algorithms and Proof Systems
ACM Transactions on Computation Theory, 2014Co-Authors: Yijia Chen, Jörg Flum, Moritz MüllerAbstract:If the class TAUT of tautologies of propositional logic has no almost optimal algorithm, then every algorithm A deciding TAUT has a hard Sequence, that is, a polynomial time Computable Sequence witnessing that A is not almost optimal. We show that this result extends to every Πt p-complete problem with t ≥1; however, assuming the Measure Hypothesis, there is a problem which has no almost optimal algorithm but is decided by an algorithm without hard Sequences. For problems Q with an almost optimal algorithm, we analyze whether every algorithm deciding Q, which is not almost optimal, has a hard Sequence.
-
CiE - Hard instances of algorithms and proof systems
Lecture Notes in Computer Science, 2012Co-Authors: Yijia Chen, Jörg Flum, Moritz MüllerAbstract:If the class Taut of tautologies of propositional logic has no almost optimal algorithm, then every algorithm $\mathbb{A}$ deciding Taut has a polynomial time Computable Sequence witnessing that $\mathbb{A}$ is not almost optimal. We show that this result extends to every $\Pi_t^p$-complete problem with t≥1; however, assuming the Measure Hypothesis, there is a problem which has no almost optimal algorithm but is decided by an algorithm without such a hard Sequence. Assuming that a problem Q has an almost optimal algorithm, we analyze whether every algorithm deciding Q, which is not almost optimal algorithm, has a hard Sequence.
Xizhong Zheng - One of the best experts on this subject based on the ideXlab platform.
-
Classification of Computably Approximable Real Numbers
Theory of Computing Systems \ Mathematical Systems Theory, 2007Co-Authors: Xizhong ZhengAbstract:A real number is called computably approximable if it is the limit of a Computable Sequence of rational numbers. Therefore the complexity of these real numbers can be classified by considering the convergence speed of Computable Sequences. In this paper we introduce a natural way to measure the convergence speed by counting the number of jumps of given sizes that appear after certain stages. Bounding the number of such kind of big jumps by different bounding functions, we introduce various classes of real numbers with different levels of approximation quality. We discuss further their mathematical properties as well as computability theoretical properties.
-
Classification of the Computable Approximations by Divergence Boundings
Electronic Notes in Theoretical Computer Science, 2007Co-Authors: Xizhong ZhengAbstract:A real number is called computably approximable if there is a Computable Sequence of rational numbers which converges to it. To investigate the complexity of computably approximable real numbers, we can consider the converging speed of the Sequences. In this paper we introduce a natural way to measure the converging speed by counting the jumps of certain size appeared after certain stages. The number of this big jumps can be bounded by a bounding function. For different choice of bounding functions, we introduce various classes of real numbers with different approximation quality and discuss their mathematical properties as well as computability theoretical properties.
-
DMTCS - On the monotonic computability of semi-Computable real numbers
Discrete Mathematics and Theoretical Computer Science, 2003Co-Authors: Xizhong Zheng, George BarmpaliasAbstract:Let h : N → Q be a Computable function. A real number x is h-monotonically Computable if there is a Computable Sequence (xs) of rational numbers which converges to x in such a way that the ratios of the approximation errors are bounded by the function h. In this paper we discuss the h-monotonic computability of semi-Computable real numbers, i.e., limits of monotone Computable Sequences of rational numbers. Especially, we show a sufficient and necessary condition for the function h such that the h-monotonic computability is simply equivalent to the normal computability.
-
Monotonically Computable Real Numbers
Mathematical Logic Quarterly, 2002Co-Authors: Robert Rettinger, Xizhong Zheng, Romain Gengler, Burchard Von BraunmühlAbstract:A real number x is called semi-Computable if it is a limit of an increasing or decreasing Computable Sequence (x n ), n∈ℕ of rational numbers. In this case, a later member of the Sequence is always a better approximation to x in the sense that |x − x n | ≥ |x − x m |, if n ≤ m. As a natural generalization, we call a real number x k-monotone Computable (k-mc, for short), for any real number k >0,, if there is a Computable Sequence (xn),n∈ℕ of rational numbers which converges to x k-monotonically in the sense that k · |x − x n | ≥ |x − x m | for any n ≤ m and x is monotonically Computable (mc, for short) if it is k-mc for some k >0. Various properties of k-mc real numbers are discussed in this paper. Among others we show that a real number is Computable if it is k-mc for some k
-
The Arithmetical Hierarchy of Real Numbers
MLQ, 2001Co-Authors: Xizhong Zheng, Klaus WeihrauchAbstract:A real number x is Computable iff it is the limit of an effectively converging Computable Sequence of rational numbers, and x is left (right) Computable iff it is the supremum (infimum) of a Computable Sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to Computable (multiple) Sequences of rational numbers we introduce a non-collapsing hierarchy {Σn, Πn, Δn : n ∈ ℕ} of real numbers. We characterize the classes Σ2, Π2 and Δ2 in various ways and give several interesting examples.
Yijia Chen - One of the best experts on this subject based on the ideXlab platform.
-
Hard Instances of Algorithms and Proof Systems
ACM Transactions on Computation Theory, 2014Co-Authors: Yijia Chen, Jörg Flum, Moritz MüllerAbstract:If the class TAUT of tautologies of propositional logic has no almost optimal algorithm, then every algorithm A deciding TAUT has a hard Sequence, that is, a polynomial time Computable Sequence witnessing that A is not almost optimal. We show that this result extends to every Πt p-complete problem with t ≥1; however, assuming the Measure Hypothesis, there is a problem which has no almost optimal algorithm but is decided by an algorithm without hard Sequences. For problems Q with an almost optimal algorithm, we analyze whether every algorithm deciding Q, which is not almost optimal, has a hard Sequence.
-
CiE - Hard instances of algorithms and proof systems
Lecture Notes in Computer Science, 2012Co-Authors: Yijia Chen, Jörg Flum, Moritz MüllerAbstract:If the class Taut of tautologies of propositional logic has no almost optimal algorithm, then every algorithm $\mathbb{A}$ deciding Taut has a polynomial time Computable Sequence witnessing that $\mathbb{A}$ is not almost optimal. We show that this result extends to every $\Pi_t^p$-complete problem with t≥1; however, assuming the Measure Hypothesis, there is a problem which has no almost optimal algorithm but is decided by an algorithm without such a hard Sequence. Assuming that a problem Q has an almost optimal algorithm, we analyze whether every algorithm deciding Q, which is not almost optimal algorithm, has a hard Sequence.
Takakazu Mori - One of the best experts on this subject based on the ideXlab platform.
-
Effective Fine‐convergence of Walsh‐Fourier series
Mathematical Logic Quarterly, 2008Co-Authors: Takakazu Mori, Mariko Yasugi, Yoshiki TsujiiAbstract:We define the effective integrability of Fine-Computable functions and effectivize some fundamental limit theorems in the theory of Lebesgue integrals such as the Bounded Convergence Theorem, the Dominated Convergence Theorem, and the Second Mean Value Theorem. It is also proved that the Walsh-Fourier coefficients of an effectively integrable Fine-Computable function form a Euclidian Computable Sequence of reals which converges effectively to zero. This property of convergence is the effectivization of the Walsh-Riemann-Lebesgue Theorem. The article is closed with the effective version of Dirichlet's test. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
-
Integral of Fine Computable functions and Walsh Fourier series
Electronic Notes in Theoretical Computer Science, 2008Co-Authors: Takakazu Mori, Mariko Yasugi, Yoshiki TsujiiAbstract:We define the effective integrability of Fine-Computable functions and effectivize some fundamental limit theorems in the theory of Lebesgue integral such as Bounded Convergence Theorem and Dominated Convergence Theorem. It is also proved that the Walsh-Fourier coefficients of an effectively integrable Fine-Computable function form an E-Computable Sequence of reals and converge effectively to zero. The latter fact is the effectivization of Walsh-Riemann-Lebesgue Theorem. The article is closed with the effective version of Dirichlet's test.
-
Effective Fine-convergence of Walsh-Fourier series
MLQ, 2008Co-Authors: Takakazu Mori, Mariko Yasugi, Yoshiki TsujiiAbstract:We define the effective integrability of Fine-Computable functions and effectivize some fundamental limit theorems in the theory of Lebesgue integrals such as the Bounded Convergence Theorem, the Dominated Convergence Theorem, and the Second Mean Value Theorem. It is also proved that the Walsh-Fourier coefficients of an effectively integrable Fine-Computable function form a Euclidian Computable Sequence of reals which converges effectively to zero. This property of convergence is the effectivization of the Walsh-Riemann-Lebesgue Theorem. The article is closed with the effective version of Dirichlet's test. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
-
Sequential Computability of a Function
Electronic Notes in Theoretical Computer Science, 2005Co-Authors: Yoshiki Tsujii, Mariko Yasugi, Takakazu MoriAbstract:We consider the real Sequences in I=0,1) and real functions on I. A computability notion with respect to the uniformity {Un}, where Un(x)=k2n,k+12n) if x∈k2n,k+12n) will be called D-computability. An R-Computable Sequence from I will be shown to be approximated by a recursive Sequence of rational numbers with a limiting recursive modulus of convergence with respect to {Un}. Using this result, we relate two extended notions of sequential computability of a function or a function Sequence, one formulated in terms of limiting recursion and one in terms of {Un}.
-
on the computability of walsh functions
Theoretical Computer Science, 2002Co-Authors: Takakazu MoriAbstract:The Haar and the Walsh functions are proved to be Computable with respect to the Fine-metric dF which is induced from the infinite product Ω = {0,1}{1,2,...} with the weighted product metric dC of the discrete metric on {0, 1}. Although they are discontinuous functions on [0, 1] with respect to the Euclidean metric, they are continuous functions on (ω, dC) and on ([0, 1], dF).On (Ω, dC), Computable real-valued cylinder functions, which include the Walsh functions, become Computable and every Computable function can be approximated effectively by a Computable Sequence of cylinder functions. The metric space ([0, 1], dF) is separable but not complete nor effectively complete. We say that a function on [0, 1] is uniformly Fine-Computable if it is sequentially Computable and effectively uniformly continuous with respect to the metric dF. It is proved that a uniformly Fine-Computable function is essentially a Computable function on Ω.It is also proved that Walsh-Fourier coefficients of a uniformly Fine-Computable function f form a Computable Sequence of reals and there exists a subSequence of the Walsh-Fourier series which Fine-converges effectively uniformly to f.
Elvira Mayordomo - One of the best experts on this subject based on the ideXlab platform.
-
effective strong dimension in algorithmic information and computational complexity
SIAM Journal on Computing, 2007Co-Authors: Krishna B Athreya, Jack H. Lutz, John M Hitchcock, Elvira MayordomoAbstract:The two most important notions of fractal dimension are Hausdorff dimension, developed by Hausdorff [Math. Ann., 79 (1919), pp. 157-179], and packing dimension, developed independently by Tricot [Math. Proc. Cambridge Philos. Soc., 91 (1982), pp. 57-74] and Sullivan [Acta Math., 153 (1984), pp. 259-277]. Both dimensions have the mathematical advantage of being defined from measures, and both have yielded extensive applications in fractal geometry and dynamical systems. Lutz [Proceedings of the 15th IEEE Conference on Computational Complexity, Florence, Italy, 2000, IEEE Computer Society Press, Piscataway, NJ, 2000, pp. 158-169] has recently proven a simple characterization of Hausdorff dimension in terms of gales, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension, including constructive, Computable, polynomial-space, polynomial-time, and finite-state dimensions. Work by several investigators has already used these effective dimensions to shed significant new light on a variety of topics in theoretical computer science. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of—and every bit as simple as—the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of effective strong dimensions, which are exact duals of the effective dimensions mentioned above. In general (and in analogy with the classical fractal dimensions), the effective strong dimension of a set or Sequence is at least as great as its effective dimension, with equality for sets or Sequences that are sufficiently regular. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression. Aside from the above characterization of packing dimension, our two main theorems are the following. 1. If $\vec{\beta} = (\beta_0,\beta_1,\ldots)$ is a Computable Sequence of biases that are bounded away from 0 and $R$ is random with respect to $\vec{\beta}$, then the dimension and strong dimension of $R$ are the lower and upper average entropies, respectively, of $\vec{\beta}$. 2. For each pair of $\Delta^0_2$-Computable real numbers $0 < \alpha \le \beta \le 1$, there exists $A \in {\rm E}$ such that the polynomial-time many-one degree of $A$ has dimension $\alpha$ in E and strong dimension $\beta$ in E. Our proofs of these theorems use a new large deviation theorem for self-information with respect to a bias Sequence $\vec{\beta}$ that need not be convergent.
-
effective strong dimension in algorithmic information and computational complexity
Lecture Notes in Computer Science, 2004Co-Authors: Krishna B Athreya, Jack H. Lutz, John M Hitchcock, Elvira MayordomoAbstract:The two most important notions of fractal dimension are Hausdorff dimension, developed by Hausdorff (1919), and packing dimension, developed independently by Tricot (1982) and Sullivan (1984). Both dimensions have the mathematical advantage of being defined from measures, and both have yielded extensive applications in fractal geometry and dynamical systems. Lutz (2000) has recently proven a simple characterization of Hausdorff dimension in terms of gales, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension, including constructive, Computable, polynomial-space, polynomial-time, and finite-state dimensions. Work by several investigators has already used these effective dimensions to shed significant new light on a variety of topics in theoretical computer science. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of - and every bit as simple as - the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of effective strong dimensions, which are exact duals of the effective dimensions mentioned above. In general (and in analogy with the classical fractal dimensions), the effective strong dimension of a set or Sequence is at least as great as its effective dimension, with equality for sets or Sequences that are sufficiently regular. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression. Aside from the above characterization of packing dimension, our two main theorems are the following. 1. If β = (β 0 , β 1 ,...) is a Computable Sequence of biases that are bounded away from 0 and R is random with respect to β, then the dimension and strong dimension of R are the lower and upper average entropies, respectively, of β. 2. For each pair of Δ 0 2-Computable real numbers 0 < a < β ≤ 1, there exists A ∈ E such that the polynomial-time many-one degree of A has dimension a in E and strong dimension β in E. Our proofs of these theorems use a new large deviation theorem for self-information with respect to a bias Sequence β that need not be convergent.
