What is a POLYNOMIAL-TIME Computable L2-Function?

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Aras Bacho, Svetlana Selivanova, Martin Ziegler
DOI: 10.48550/arxiv.2601.17078
Cited by: 0

Abstract

We give two natural definitions of polynomial-time computability for L2 functions; and we show them incomparable (unless complexity class FP_1 includes #P_1).

Fields of Study & Subjects

Computability Logic AI Algorithms Complexity and Algorithms in Graphs Quantum Computing Algorithms and Architecture

Publication details

Journal / source
arXiv (Cornell University)
Publication date
23 January 2026
Document type
Preprint