Cover Image

Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kratsios, Anastasis, Zvigelsky, Dennis, Hart, Bradd
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity Logic in Computer Science Numerical Analysis Neural and Evolutionary Computing 68T07, 68Q17, 68Q05, 68W40, 68N99
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
by: Opris, Andre, et al.
Published: (2024)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Runtime Analyses of NSGA-III on Many-Objective Problems
by: Opris, Andre, et al.
Published: (2024)

A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy
by: Opris, Andre
Published: (2025)

Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
by: Opris, Andre
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data
by: Kratsios, Anastasis, et al.
Published: (2025)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Teaching and Learning under Deductive Errors
by: Telle, Jan Arne, et al.
Published: (2026)

Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity
by: Kratsios, Anastasis, et al.
Published: (2026)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
by: Zhang, Weikun K., et al.
Published: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Many Objective Problems Where Crossover is Provably Essential
by: Opris, Andre
Published: (2024)

Dynamic T-decomposition for classical simulation of quantum circuits
by: Ahmad, Wira Azmoon, et al.
Published: (2024)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning
by: Kratsios, Anastasis, et al.
Published: (2026)

Survey of Genetic and Differential Evolutionary Algorithm Approaches to Search Documents Based On Semantic Similarity
by: Muniyappa, Chandrashekar, et al.
Published: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

pETNNs: Partial Evolutionary Tensor Neural Networks for Solving Time-dependent Partial Differential Equations
by: Kao, Tunan, et al.
Published: (2024)

When can forward stable algorithms be composed stably?
by: Beltrán, Carlos, et al.
Published: (2021)

Provability in BI's Sequent Calculus is Decidable
by: Gheorghiu, Alexander, et al.
Published: (2021)

Optimal Simultaneous Byzantine Agreement, Common Knowledge and Limited Information Exchange
by: van der Meyden, Ron
Published: (2025)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)