:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Cattabriga, Paola
Format:	Preprint
Published:	2013
Subjects:	Computational Complexity Logic in Computer Science 03D10, 68Qxx
Online Access:	https://arxiv.org/abs/1308.0497
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Refutability as Recursive as Provability
by: Cattabriga, Paola
Published: (2024)

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
by: Dutta, Pranjal, et al.
Published: (2023)

On Godel's treatment of the undecidable in 1931
by: Cattabriga, Paola
Published: (2024)

Quantum Random Self-Modifiable Computation
by: Fiske, Michael Stephen
Published: (2018)

A Minimal Substitution Basis for the Kalmár Elementary Functions
by: Prunescu, Mihai, et al.
Published: (2025)

Reflections on Russell's antinomy
by: Cattabriga, Paola
Published: (2024)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Semi-Algebraic Proof Systems for QBF
by: Beyersdorff, Olaf, et al.
Published: (2025)

Biological arrow of time: Emergence of tangled information hierarchies and self-modelling dynamics
by: Prokopenko, Mikhail, et al.
Published: (2024)

A Formal Analysis of Algorithms for Matroids and Greedoids
by: Abdulaziz, Mohammad, et al.
Published: (2025)

Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
by: Nevin, Joshua
Published: (2025)

On a bi-lateral Adding Machine and its characterization
by: Mehdipour, Pouya, et al.
Published: (2025)

Choiceless Polynomial Space
by: Ferrarotti, Flavio, et al.
Published: (2024)

Computational Complexity of Model-Checking Quantum Pushdown Systems
by: Lin, Deren, et al.
Published: (2025)

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index
by: Sorg, Christopher
Published: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Finitely Bounded Homogeneity Turned Inside-Out
by: Rydval, Jakub
Published: (2021)

A proof of P!=NP
by: McCallum, Rupert
Published: (2020)

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
by: Kattermann, David, et al.
Published: (2025)

Fast LDL factorization for dense and sparse symmetric matrices over an arbitrary field
by: Solomonik, Edgar
Published: (2025)

Towards a Measure of Algorithm Similarity
by: Sohail, Shairoz, et al.
Published: (2025)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

On Chaitin's Heuristic Principle and Halting Probability
by: Salehi, Saeed
Published: (2023)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

There is a deep 1-generic set
by: Li, Ang
Published: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

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

Online and feasible presentability: from trees to modal algebras
by: Bazhenov, Nikolay, et al.
Published: (2025)

Algebra of Self-Replication
by: Moss, Lawrence S.
Published: (2023)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

Formalising New Mathematics in Isabelle: Diagonal Ramsey
by: Paulson, Lawrence C
Published: (2025)

An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees
by: Samra, Jean Abou, et al.
Published: (2026)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Variants of Solovay reducibility
by: Titov, Ivan
Published: (2024)

On the incomputability of computable dimension
by: Staiger, Ludwig
Published: (2019)

On Some Complexity Results for Even Linear Languages
by: Cojocaru, Liliana
Published: (2024)

The strength of Ramsey Theorem for coloring relatively large sets
by: Carlucci, Lorenzo, et al.
Published: (2012)