A Computational Complexity Theory in Membrane Computing [PDF]
Workshop on Membrane Computing, 2010 In this paper, a computational complexity theory within the framework of Membrane Computing is introduced. Polynomial complexity classes associated with di erent models of cell-like and tissue-like membrane systems are de ned and the most relevant ...
A. Alhazov +31 more
core +3 more sources
Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory [PDF]
, 2009 One of the central problems in quantum mechanics is to determine the ground state properties of a system of electrons interacting via the Coulomb potential.
A Auerbach +16 more
core +5 more sources
Computational complexity of vacua and near-vacua in field and string theory [PDF]
Physical Review D, 2019 We demonstrate that the problems of finding stable or metastable vacua in a low energy effective field theory requires solving nested NP-hard and co-NP-hard problems, while the problem of finding near-vacua is in P.
James Halverson, Fabian Ruehle
openalex +3 more sources
On The Computational Complexity of Self-Attention [PDF]
International Conference on Algorithmic Learning Theory, 2022 Transformer architectures have led to remarkable progress in many state-of-art applications. However, despite their successes, modern transformers rely on the self-attention mechanism, whose time- and space-complexity is quadratic in the length of the ...
Feyza Duman Keles +2 more
semanticscholar +1 more source
Computational Complexity in Algebraic Combinatorics [PDF]
arXiv.org, 2023 Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives and brought us some beautiful ...
G. Panova
semanticscholar +1 more source
P Systems with Evolutional Communication and Division Rules
Axioms, 2021 A widely studied field in the framework of membrane computing is computational complexity theory. While some types of P systems are only capable of efficiently solving problems from the class P, adding one or more syntactic or semantic ingredients to ...
David Orellana-Martín +2 more
doaj +1 more source
An Overview of the Theory of Computational Complexity [PDF]
JACM, 1971 Juris Hartmanis, John E. Hopcroft
openalex +2 more sources
The future of computational complexity theory: part II [PDF]
SIGA, 1996 Eric Allender +4 more
openalex +2 more sources
Computational Creativity and Aesthetics with Algorithmic Information Theory
Entropy, 2021 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.
Tiasa Mondol, Daniel G. Brown
doaj +1 more source
Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces [PDF]
Foundations of Computational Mathematics, 2021 We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks.
P. Grohs, F. Voigtlaender
semanticscholar +1 more source