Buchumschlag

On Equivalent Characterizations of NP in Abstract Models of Computation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kirn, Jeremy C., Meijer, Lucas, Miltzow, Tillmann, Bodlaender, Hans L.
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Logic in Computer Science 68Q19 F.1.1
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Place Bisimilarity is Decidable, Indeed!
von: Gorrieri, Roberto
Veröffentlicht: (2021)

Probabilistic Nets-within-Nets
von: Köhler-Bußmeier, Michael
Veröffentlicht: (2024)

A "Symbolic" Representation of Object-Nets (Extended Version)
von: Köhler-Bussmeier, Michael, et al.
Veröffentlicht: (2024)

Reversible computations are computations
von: Aubert, Clément, et al.
Veröffentlicht: (2025)

Decidable Reversible Equivalences for Finite Petri Nets
von: Gorrieri, Roberto, et al.
Veröffentlicht: (2025)

Commutative N-polyregular functions
von: Lopez, Aliaume
Veröffentlicht: (2024)

On the existence of strong proof complexity generators
von: Krajicek, Jan
Veröffentlicht: (2022)

Oracle Separations for RPH
von: Hamm, Thekla, et al.
Veröffentlicht: (2025)

A Logspace Constructive Proof of L=SL
von: Buss, Sam, et al.
Veröffentlicht: (2025)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
von: Schewe, Klaus-Dieter
Veröffentlicht: (2020)

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
von: Adsul, Bharat, et al.
Veröffentlicht: (2024)

The Algebra of Nondeterministic Finite Automata
von: Gorrieri, Roberto
Veröffentlicht: (2023)

Axiomatizing NFAs Generated by Regular Grammars
von: Gorrieri, Roberto
Veröffentlicht: (2024)

Learning Closed Signal Flow Graphs
von: Piotrovskaya, Ekaterina, et al.
Veröffentlicht: (2024)

Bishop's (up)crossing inequality and lower semicomputable random reals revisited
von: Andreev, Mikhail, et al.
Veröffentlicht: (2025)

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

Algebra of Self-Replication
von: Moss, Lawrence S.
Veröffentlicht: (2023)

Simulating and model checking membrane systems using strategies in Maude
von: Rubio, Rubén, et al.
Veröffentlicht: (2024)

Extended Nullstellensatz proof systems
von: Krajicek, Jan
Veröffentlicht: (2023)

Model checking strategy-controlled systems in rewriting logic
von: Rubio, Rubén, et al.
Veröffentlicht: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
von: Huseynzade, Rafig
Veröffentlicht: (2025)

Computability of Initial Value Problems
von: Brattka, Vasco, et al.
Veröffentlicht: (2024)

$Δ$-Nets: Interaction-Based System for Optimal Parallel $λ$-Reduction
von: Salvadori, Daniel Augusto Rizzi
Veröffentlicht: (2025)

Relative Constructibility via Generalised Sequential Algorithms
von: Lau, Desmond
Veröffentlicht: (2024)

Strategies, model checking and branching-time properties in Maude
von: Rubio, Rubén, et al.
Veröffentlicht: (2024)

Metalevel transformation of strategies
von: Rubio, Rubén, et al.
Veröffentlicht: (2024)

Monitoring Hyperproperties over Observed and Constructed Traces
von: Chalupa, Marek, et al.
Veröffentlicht: (2025)

Principal Types as Partial Involutions
von: Honsell, Furio, et al.
Veröffentlicht: (2024)

Graded Monad Coalgebras for Continuous-Time Transition Systems
von: Di Lavore, Elena, et al.
Veröffentlicht: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
von: von Liechtenstein, Maximilian R. P.
Veröffentlicht: (2025)

Arithmetics within the Linear Time Hierarchy
von: Pollett, Chris
Veröffentlicht: (2025)

Descriptive complexity for neural networks via Boolean networks
von: Ahvonen, Veeti, et al.
Veröffentlicht: (2023)

Graded Monads in the Semantics of Nominal Automata
von: Schulze, Hannes, et al.
Veröffentlicht: (2025)

A correspondence between the time and space complexity
von: Latkin, Ivan V.
Veröffentlicht: (2023)

QSeqSim: A Symbolic Simulator for Qiskit While Loops Using Sequential Quantum Circuits
von: Li, Zihao, et al.
Veröffentlicht: (2026)

On Woolhouse's Cotton-Spinning Problem
von: Groote, Jan Friso, et al.
Veröffentlicht: (2024)

The Solver's Paradox in Formal Problem Spaces
von: Rosko, Milan
Veröffentlicht: (2025)

A Qualitative Analysis of Kernel Extension for Higher Order Proof Checking
von: Wang, Shuai
Veröffentlicht: (2024)

A proof complexity conjecture and the Incompleteness theorem
von: Krajicek, Jan
Veröffentlicht: (2023)

On the Realizability of Prime Conjectures in Heyting Arithmetic
von: Rosko, Milan
Veröffentlicht: (2025)