Cover Image

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Huseynzade, Rafig
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Formal Languages and Automata Theory Logic in Computer Science 68Q15 (Primary) 68Q05, 68Q17, 03D15 (Secondary) F.1.3; F.1.1; F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
by: Adsul, Bharat, et al.
Published: (2024)

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

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)

The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)

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

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Arithmetics within the Linear Time Hierarchy
by: Pollett, Chris
Published: (2025)

The Algebra of Nondeterministic Finite Automata
by: Gorrieri, Roberto
Published: (2023)

Axiomatizing NFAs Generated by Regular Grammars
by: Gorrieri, Roberto
Published: (2024)

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

$\mathbb{N}$-polyregular functions arise from well-quasi-orderings
by: Lopez, Aliaume
Published: (2024)

Decision Problems on Copying and Shuffling
by: Halava, Vesa, et al.
Published: (2023)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Disproving Termination of Non-Erasing Sole Combinatory Calculus with Tree Automata (Full Version)
by: Nakano, Keisuke, et al.
Published: (2024)

Normal forms in Virus Machines
by: Ramírez-de-Arellano, A., et al.
Published: (2024)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
by: Bruse, Florian, et al.
Published: (2026)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
by: Cho, Da-Jung, et al.
Published: (2025)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
by: Dörfler, Julian, et al.
Published: (2024)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

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

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)

Classically Time-Controlled Quantum Automata: Definition and Properties
by: Díaz-Caro, Alejandro, et al.
Published: (2018)

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

Hypernode Automata
by: Bartocci, Ezio, et al.
Published: (2023)

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

Determination of the fifth Busy Beaver value
by: The bbchallenge Collaboration, et al.
Published: (2025)

A Logic For Fresh Labelled Transition Systems
by: Bandukara, Mohamed H, et al.
Published: (2025)

Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words
by: Zubia, Markel, et al.
Published: (2026)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)