Cover Image

Constructibility and the P versus NP problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Hole, Arne
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Logic in Computer Science F.0, F.1.3, F.2.0, F.4.0 F.0; F.1.3; F.2.0; F.4.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Note on the NP-Hardness of PARTITION Via First-Order Projections
by: Iturralde, Paúl Risco
Published: (2025)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

Serial Properties, Selector Proofs, and the Provability of Consistency
by: Artemov, Sergei
Published: (2024)

Non-Compact Proofs
by: Artemov, Sergei
Published: (2025)

Consistency formula is strictly stronger in PA than PA-consistency
by: Artemov, Sergei
Published: (2025)

A Complete Axiomatisation of Equivalence for Discrete Probabilistic Programming
by: Piedeleu, Robin, et al.
Published: (2024)

Different Theories of Parts
by: Pietruszczak, Andrzej
Published: (2024)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

On the $p$-adic Skolem Problem
by: Bacik, Piotr, et al.
Published: (2025)

Probabilistic Shoenfield Machines
by: Bujok, Maksymilian, et al.
Published: (2024)

Neural networks as fuzzy logic formulas
by: Heiman, Damian, et al.
Published: (2026)

On the Decidability of Verification under Release/Acquire
by: Conrado, Giovanna Kobus, et al.
Published: (2026)

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

Ranking Functions for Linear-Constraint Loops
by: Ben-Amram, Amir M., et al.
Published: (2012)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Realizable Circuit Complexity: Embedding Computation in Space-Time
by: Prada, Benjamin, et al.
Published: (2025)

OnlineProver: Experience with a Visualisation Tool for Teaching Formal Proofs
by: Perháč, Ján, et al.
Published: (2025)

Constructive Cavity Method
by: Franchini, Simone
Published: (2026)

Universal Algebra in UniMath
by: Amato, Gianluca, et al.
Published: (2020)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

A Theory of Hanoi Omega-Automata and Games
by: Filiot, Emmanuel, et al.
Published: (2026)

Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
by: Ahvonen, Veeti, et al.
Published: (2024)

Expressive Power of Graph Transformers via Logic
by: Ahvonen, Veeti, et al.
Published: (2025)

Graph neural networks and MSO
by: Ahvonen, Veeti, et al.
Published: (2025)

Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
by: Ahvonen, Veeti, et al.
Published: (2026)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Graphical Quadratic Algebra
by: Stein, Dario, et al.
Published: (2024)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

Fixed-Point Theorems and the Ethics of Radical Transparency: A Logic-First Treatment
by: Alpay, Faruk, et al.
Published: (2025)

Proof-Carrying Neuro-Symbolic Code
by: Komendantskaya, Ekaterina
Published: (2025)

Graded modal logic and counting message passing automata
by: Ahvonen, Veeti, et al.
Published: (2024)

On the Pure States of the Replica Symmetry Breaking ansatz
by: Franchini, Simone
Published: (2025)

Online Paging with Heterogeneous Cache Slots
by: Chrobak, Marek, et al.
Published: (2022)

INTERLEAVE: A Faster Symbolic Algorithm for Maximal End Component Decomposition
by: Bansal, Suguman, et al.
Published: (2025)

Thinking Like a Student: AI-Supported Reflective Planning in a Theory-Intensive Computer Science Course
by: Izsak, Noa
Published: (2025)

The Fractal Logic of Phi-adic Recursion
by: Rosko, Milan
Published: (2025)