Home // COMPUTATION TOOLS 2018, The Ninth International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking // View article

Diagonalization and the Complexity of Programs

Authors:
Emanuele Covino
Giovanni Pani

Keywords: Hierachies of complexity classes; Predicative recursion; Constructive diagonalization.

Abstract:
Starting from the definitions of predicative recursion and constructive diagonalization, we recall our specialized programming language that provides a resource-free characterization of register machines computing their output within polynomial time O(n^k), and exponential time O(n^{n^k}), for each finite k. We discuss the possibility of extending this characterization to a transfinite hierarchy of programs that captures the Grzegorczyk hierarchy of functions at elementary level. This is done by means of predicative operators, contrasting to previous results. We discuss the feasibility and the complexity of our diagonalization operator.

Pages: 1 to 5

Copyright: Copyright (c) IARIA, 2018

Publication date: February 18, 2018

Published in: conference

ISSN: 2308-4170

ISBN: 978-1-61208-613-2

Location: Barcelona, Spain

Dates: from February 18, 2018 to February 22, 2018