اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHow incomputable is Kolmogorov complexity?
82
0
0.0
(
0
)
تأليف
Paul Vitanyi
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Kolmogorov complexity is the length of the ultimately compressed version of a file (that is, anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. We discuss the incomputabilty of Kolmogorov complexity, which formal loopholes this leaves us, recent approaches to compute or approximate Kolmogorov complexity, which approaches are problematic and which approaches are viable.
قيم البحث
اقرأ أيضاً
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (H
ammer et al., 1997), as well as for sizes of subgroups and projections of sets (Chan, Yeung, Romashchenko, Shen, Vereshchagin, 1998--2002). This parallelism started with the Kolmogorov-Levin formula (1968) for the complexity of pairs of strings with logarithmic precision. Longpre (1986) proved a version of this formula for space-bounded complexities. In this paper we prove an improved version of Longpres result with a tighter space bound, using Sipsers trick (1980). Then, using this space bound, we show that every linear inequality that is true for complexities or entropies, is also true for space-bounded Kolmogorov complexities with a polynomial space overhead.
The quantum complexity of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. While the notion of quantum complexity was first introduced as a quantum generalization of the classical computational co
mplexity, it has since been argued to hold a fundamental significance in its own right, as a physical quantity analogous to the thermodynamic entropy. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators. One striking feature of these functions is that they can exhibit non-smooth and even fractal behaviour. We use ideas from Diophantine approximation theory and sub-Riemannian geometry to rigorously quantify this lack of smoothness. Implications for the physical meaning of quantum complexity are discussed.
We investigate the relationship between Orthogonal Time Frequency Space (OTFS) modulation and Orthogonal Short Time Fourier (OSTF) signaling. OTFS was recently proposed as a new scheme for high Doppler scenarios and builds on OSTF. We first show that
the two schemes are unitarily equivalent in the digital domain. However, OSTF defines the analog-digital interface with the waveform domain. We then develop a critically sampled matrix-vector model for the two systems and consider linear minimum mean-squared error (MMSE) filtering at the receiver to suppress inter-symbol interference. Initial comparison of capacity and (uncoded) probability of error reveals a surprising observation: OTFS under-performs OSTF in capacity but over-performs in probability of error. This result can be attributed to characteristics of the channel matrices induced by the two systems. In particular, the diagonal entries of OTFS matrix exhibit nearly identical magnitude, whereas those of the OSTF matrix exhibit wild fluctuations induced by multipath randomness. It is observed that by simply replacing the unitary matrix, relating OTFS to OSTF, by an arbitrary unitary matrix results in performance nearly identical to OTFS. We then extend our analysis to orthogonal frequency division multiplexing (OFDM) and also consider a more extreme scenario of relatively large delay and Doppler spreads. Our results demonstrate the significance of using OSTF basis waveforms rather than sinusoidal ones in OFDM in highly dynamic environments, and also highlight the impact of the level of channel state information used at the receiver.
Suppose a Boolean function $f$ is symmetric under a group action $G$ acting on the $n$ bits of the input. For which $G$ does this mean $f$ does not have an exponential quantum speedup? Is there a characterization of how rich $G$ must be before the fu
nction $f$ cannot have enough structure for quantum algorithms to exploit? In this work, we make several steps towards understanding the group actions $G$ which are quantum intolerant in this way. We show that sufficiently transitive group actions do not allow a quantum speedup, and that a well-shuffling property of group actions -- which happens to be preserved by several natural transformations -- implies a lack of super-polynomial speedups for functions symmetric under the group action. Our techniques are motivated by a recent paper by Chailloux (2018), which deals with the case where $G=S_n$. Our main application is for graph symmetries: we show that any Boolean function $f$ defined on the adjacency matrix of a graph (and symmetric under relabeling the vertices of the graph) has a power $6$ relationship between its randomized and quantum query complexities, even if $f$ is a partial function. In particular, this means no graph property testing problems can have super-polynomial quantum speedups, settling an open problem of Ambainis, Childs, and Liu (2011).
We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density $> 1$ and also to quantum sampling subset sum solutions. We examine a decision versio
n of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density $>1$. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density $>1$ but approaching $1$ as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
