26 papers · ranked by Valyu relevance
John S. Nicolis
Finally, it gives a complete proof that a certain decision problem in NP has an algorithmic exponential lower bound thus establishing firmly that P≠NP. The proof presents a new way of approaching the subject: neither by entering into the unmanageable difficulties of proving this type of lower bound for the known…
Paul Vitányi
A Turing machine refers to a hypothetical machine proposed by Alan M. Turing (1912–1954) in 1936 [11] whose computations are intended to give an operational and formal definition of the intuitive notion of computability in the discrete domain. It is a digital device and sufficiently simple to be amenable to theoretical…
Davide Cirillo, Alfonso Valencia
Computational problems can be classified according to their algorithmic complexity, which is defined based on how the computational resources needed to solve the problem scale with the problem size. In particular, computationally intractable problems are often solved through heuristics or approximations so to overcome…
Feng Pan, Heng-Liang Zhang, Jie Qi
Computational complexity is a particularly important objective. The idea of Landauer principle was extended through mapping three classic problems (sorting、 ordered searching and max of N unordered numbers) into Maxwell demon thought experiment in this paper. The problems' complexity is defined on the entropy basis and…
James Whitfield, Peter J. Love, Alán Aspuru‐Guzik
In quantum chemistry, the price paid by all known efficient model chemistries is either the truncation of the Hilbert space or uncontrolled approximations. Theoretical computer science suggests that these restrictions are not mere shortcomings of the algorithm designers and programmers but could stem from the inherent…
Andrew Currin, Konstantin Korovin, Maria Ababi, Katherine Roper + 3 more
'Douglas B. Kell' 'Philip J. Day' 'Ross D. King'] The theory of computer science is based around universal Turing machines (UTMs): abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of classical UTMs. For the most important class of problem in computer science…
Pier Luigi Gentili
The goals and targets included in the 2030 Agenda compiled by the United Nations want to stimulate action in areas of critical importance for humanity and the Earth. These goals and targets regard everyone on Earth from both the health and economic and social perspectives. Reaching these goals means to deal with…
Hajo Broersma, Susan Stepney, Göran Wendin
For many decades, Moore's Law (Moore; 1965) gave us exponentially-increasing classical (digital) computing (CCOMP) power, with a doubling time of around 18 months. This cannot continue indefinitely, due to ultimate physical limits (Lloyd; 2000). Well before then, more practical limits will slow this increase. One such…
Juan P. Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts + 1 more
The survival of human organisms depends on our ability to solve complex tasks in the face of limited cognitive resources. However, little is known about the factors that drive the complexity of those tasks. Here, building on insights from computational complexity theory, we quantify the computational hardness of…
Anurag Dutta, K. Lakshmanan, John Harshith, Aditya Ramamoorthy
—Time Complexity is an important metric to compare algorithms based on their cardinality. The commonly used, trivial notations to qualify the same are the Big-Oh, Big-Omega, Big-Theta, Small-Oh, and Small-Omega Notations. All of them, consider time a part of the real entity, i.e., Time coincides with the horizontal…
Christopher P. Kempes, Michael Lachmann, Andrew Iannaccone, G. Matthew Fricke + 3 more
'G. Matthew Fricke' 'M. Redwan Chowdhury' 'Sara I. Walker' 'Leroy Cronin'] Assembly theory (AT) quantifies selection using the assembly equation, identifying complex objects through the assembly index, the minimal steps required to build an object from basic parts, and copy number, the observed instances of the object.…
Tao Hong, William R. Stauffer
Complex economic decisions are often combinatorial: they require individuals to select from many alternatives under strict constraints on time, resources, and energy. Combinatorial reasoning is the cognitive process that enables decision makers to construct and evaluate multiple potential solutions in the face of these…
Juan Pablo Franco, Nitin Yadav, Peter Bossaerts, Carsten Murawski
Life presents us with decisions of varying degrees of difficulty. Many of them are NP-hard, that is, they are computationally intractable. Two important questions arise: which properties of decisions drive extreme computational hardness and what are the effects of these properties on human-decision making? Here, we…
Asad Malik
There is a cognitive limit in Human Mind. This cognitive limit has played a decisive role in almost all fields including computer sciences. The cognitive limit replicated in computer sciences is responsible for inherent Computational Complexity. The complexity starts decreasing if certain conditions are met, even…
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent…
Anamika Agrawal, Michael A. Buice
The simple linear threshold units used in many artificial neural networks have a limited computational capacity. Famously, a single unit cannot handle non-linearly separable problems like XOR. In contrast, real neurons exhibit complex morphologies as well as active dendritic integration, suggesting that their…
Murat Erkurt
We investigate chaoticity and complexity of a binary general network automata of finite size with external input which we call a computron. As a generalization of cellular automata, computrons can have non-uniform cell rules, non-regular cell connectivity and an external input. We show that any finite-state machine can…
Tiasa Mondol, Daniel G. Brown, Ercan Kuruoglu
We build an analysis based on the Algorithmic Information Theory of computational creativity and extend it to revisit computational aesthetics, thereby, improving on the existing efforts of its formulation. We discuss Kolmogorov complexity, models and randomness deficiency (which is a measure of how much a model falls…
Hector Zenil, Narsis A. Kiani, Francesco Marabita, Yue Deng + 4 more
It remains fundamentally unclear how to reprogram complex evolving systems. Here, we introduce a conceptual framework and an interventional calculus to steer and manipulate systems based on their intrinsic algorithmic probability using the universal principles of the theory of computability and algorithmic information.…
Authors not listed
The era of exascale computing presents both exciting opportunities and unique challenges for quantum mechanical simulations. While the transition from petaflops to exascale computing has been marked by a steady increase in computational power, the shift towards heterogeneous architectures, particularly the dominant…
Authors not listed
The Hidden Subgroup Problem (HSP) unifies several landmark quantum algorithms, yet systematic exploration of its variants and modern applications has slowed. This paper revives HSP-based algorithm design by examining new group structures with direct relevance to post-quantum cryptography, lattice problems, and…
Ruben Sanchez-Garcia, Dávid Havasi, Gergely Takács, Matthew C. Robinson + 3 more
Compound availability is a critical property for design prioritization across the drug discovery pipeline. Historically, and despite their multiple limitations, compound-oriented synthetic accessibility scores have been used as proxies for this problem. However, the size of the catalogues of commercially available…
Ruben Sanchez-Garcia, Dávid Havasi, Gergely Takács, Matthew C. Robinson + 3 more
Compound availability is a critical property for design prioritization across the drug discovery pipeline. Historically, and despite their multiple limitations, compound-oriented synthetic accessibility scores have been used as proxies for this problem. However, the size of the catalogues of commercially available…
Clare Horsman, Susan Stepney, Rob C. Wagner, Viv Kendon
Computing is a high-level process of a physical system. Recent interest in non-standard computing systems, including quantum and biological computers, has brought this physical basis of computing to the forefront. There has been, however, no consensus on how to tell if a given physical system is acting as a computer or…
Authors not listed
Step-by-step thinking is essential in all domains of chemical sciences and engineering. While machine learning tools are broadly used, algorithms that automate reasoning are far less common. We elaborate on seven categories of human reasoning activities and connect each to applications in chemical science and…
Authors not listed
This work establishes theoretical foundations for hierarchical quantum-classical algorithm design, where complex problems are decomposed across multiple spatial, temporal, or organizational scales with quantum and classical computation assigned to appropriate levels. We develop a mathematical framework that…