We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to repr...
详细信息
We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with, a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.
This paper is a survey of concepts and results related to simple Kolmogorov complexity, prefix complexity and resource-bounded complexity, We also consider a new type of complexity-statistical complexity closely relat...
详细信息
This paper is a survey of concepts and results related to simple Kolmogorov complexity, prefix complexity and resource-bounded complexity, We also consider a new type of complexity-statistical complexity closely related to mathematical statistics, Unlike other discoverers of algorithmic complexityt. A. N. Kolmogorov's leading motive was developing on its basis a mathematical theory more adequately substantiating applications of probability theory, mathematical statistics and information theory, Kolmogorov wanted to deduce properties of a random object from its complexity characteristics without use of the notion of probability, In the first part of this paper me present several results in this direction. Though the subsequent development of algorithmic complexity and randomness tvas different, algorithmic complexity has successful applications in a traditional probabilistic framework, In the second part of the paper me consider applications to the estimation of parameters and the definition of Bernoulli sequences. All considerations have finite combinatorial character.
Computer-based shape grammar implementations aim to support creative design exploration by automating rule-application. This paper reviews existing shape grammar implementations in terms of their algorithmic complexit...
详细信息
Computer-based shape grammar implementations aim to support creative design exploration by automating rule-application. This paper reviews existing shape grammar implementations in terms of their algorithmic complexity, extends the definition of shape grammars with sets of transformations for rule application, categorizes (parametric and non-parametric) sets of transformations, and analyses these categories in terms of the resulting algorithmic complexity. Specifically, it describes how different sets of transformations admit different numbers of targets (i.e., potential inputs) for rule application. In the non-parametric case, this number is quadratic or cubic, while in the parametric case, it can be non-polynomial, depending on the size of the target shape. The analysis thus yields lower bounds for the algorithmic complexity of shape grammar implementations that hold independently of the employed algorithm or data structure. Based on these bounds, we propose novel matching algorithms for non-parametric and parametric shape grammar implementation and analyze their complexity. The results provide guidance for future, general-purpose shape grammar implementations for design exploration.
For a simplest mathematical model of a stock market, the problem of optimal distribution of investments among different securities (stocks, bonds, etc.) is considered. Our results, which are obtained in terms of algor...
详细信息
For a simplest mathematical model of a stock market, the problem of optimal distribution of investments among different securities (stocks, bonds, etc.) is considered. Our results, which are obtained in terms of algorithmic complexity, allow to discuss heuristically the properties of sufficiently complex security portfolios in the conditions of daily changing return rates. All considerations are given in the combinatorial framework and do not use any probabilistic models.
Idiopathic rapid eye movement sleep behavior disorder (RBD) is a serious risk factor for neurodegenerative processes such as Parkinson's disease (PD). We investigate the use of EEG algorithmic complexity derived m...
详细信息
Idiopathic rapid eye movement sleep behavior disorder (RBD) is a serious risk factor for neurodegenerative processes such as Parkinson's disease (PD). We investigate the use of EEG algorithmic complexity derived metrics for its prognosis. We analyzed resting state EEG data collected from 114 idiopathic RBD patients and 83 healthy controls in a longitudinal study forming a cohort in which several RBD patients developed PD or dementia with Lewy bodies. Multichannel data from similar to 3 min recordings was converted to spectrograms and their algorithmic complexity estimated using Lempel-Ziv-Welch compression. complexity measures and entropy rate displayed statistically significant differences between groups. Results are compared to those using the ratio of slow to fast frequency power, which they are seen to complement by displaying increased sensitivity even when using a few EEG channels. Poor prognosis in RBD appears to be associated with decreased complexity of EEG spectrograms stemming in part from frequency power imbalances and cross-frequency amplitude algorithmic coupling. algorithmic complexity metrics provide a robust, powerful and complementary way to quantify the dynamics of EEG signals in RBD with links to emerging theories of brain function stemming from algorithmic information theory.
A theory of algorithmic complexity from computer science allows one to examine the properties of algorithms for the solution of computational problems and, in particular, the relationship between the size of an instan...
详细信息
A theory of algorithmic complexity from computer science allows one to examine the properties of algorithms for the solution of computational problems and, in particular, the relationship between the size of an instance of the generic problem and the time required for computation The theory identifies certain problems asnp- complete ornp-hard, two classes of problems thought to be intractable. We show that three problems from computational statistics arenp- hard: cluster analysis, subset selection in regression andD-optimal exact design of experiments.
Properties of the idempotently convex hull of a two-point set in a free semimodule over the idempotent semiring R-max min and in a free semimodule over a linearly ordered idempotent semifield are studied. Construction...
详细信息
Properties of the idempotently convex hull of a two-point set in a free semimodule over the idempotent semiring R-max min and in a free semimodule over a linearly ordered idempotent semifield are studied. Construction algorithms for this hull are proposed.
Previously, a lot of research has been done on scheduling a finite set of mixed criticality jobs with two levels of criticality on a single processor, which is also the subject of this work. It has been claimed that t...
详细信息
ISBN:
(纸本)9781450364638
Previously, a lot of research has been done on scheduling a finite set of mixed criticality jobs with two levels of criticality on a single processor, which is also the subject of this work. It has been claimed that testing the correctness of solutions for this scheduling problem can be done in polynomial time. In this paper, we give a counter example to one of the lemmas used in that proof, reopening the question on whether the scheduling problem is in class NP. Taking into account our counter example, the authors who initially proved that correctness testing can be done in polynomial time published a fix to their proof. In the past, we proved that a previously existing correctness test is applicable for a quite general class of policies. From these results, for essentially the same class of policies, in this work we derive another correctness test, which transforms the policy to a new policy having a set of time-triggered tables, one for each criticality level. We show that the two policies are equivalent, in the sense that if one successfully schedules a jobs instance then so does the other. Thus the new transformed policy can be used for testing correctness of the original policy. We show that this correctness test has a lower algorithmic complexity than the existing test, due to the fact that the testing is done on only two static tables.
This paper analyzes the algorithmic complexity (also known as Kolmogorov complexity or descriptive complexity) of the lemma corpus included in the Wortfamilienw & ouml;rterbuch der deutschen Gegenwartssprache (WfW...
详细信息
This paper analyzes the algorithmic complexity (also known as Kolmogorov complexity or descriptive complexity) of the lemma corpus included in the Wortfamilienw & ouml;rterbuch der deutschen Gegenwartssprache (WfWG;Augst 2009) as a function of its macrostructural arrangement. The results show that, compared to the alphabetical order, the WfWG word-family arrangement produces an algorithmically more compressible, and therefore less complex version of the lemma corpus. This observation points to a higher degree of learnability and cognitive accessibility of the lemma corpus arranged in word families.
As human randomness production has come to be more closely studied and used to assess executive functions (especially inhibition), many normative measures for assessing the degree to which a sequence is randomlike hav...
详细信息
As human randomness production has come to be more closely studied and used to assess executive functions (especially inhibition), many normative measures for assessing the degree to which a sequence is randomlike have been suggested. However, each of these measures focuses on one feature of randomness, leading researchers to have to use multiple measures. Although algorithmic complexity has been suggested as a means for overcoming this inconvenience, it has never been used, because standard Kolmogorov complexity is inapplicable to short strings (e. g., of length l <= 50), due to both computational and theoretical limitations. Here, we describe a novel technique (the coding theorem method) based on the calculation of a universal distribution, which yields an objective and universal measure of algorithmic complexity for short strings that approximates Kolmogorov-Chaitin complexity.
暂无评论