Copertina

Insignificant Choice Polynomial Time: A Logic Capturing PTIME

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Schewe, Klaus-Dieter
Natura:	Preprint
Pubblicazione:	2020
Soggetti:	Computational Complexity Logic in Computer Science 68Q05, 68Q10, 03D10 F.1.3; F.1.1; F.4.1
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Extended Nullstellensatz proof systems
di: Krajicek, Jan
Pubblicazione: (2023)

On the existence of strong proof complexity generators
di: Krajicek, Jan
Pubblicazione: (2022)

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

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

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

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

Relative Constructibility via Generalised Sequential Algorithms
di: Lau, Desmond
Pubblicazione: (2024)

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

Adversarial Barrier in Uniform Class Separation
di: Rosko, Milan
Pubblicazione: (2025)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
di: Bannach, Max, et al.
Pubblicazione: (2025)

On the Realizability of Prime Conjectures in Heyting Arithmetic
di: Rosko, Milan
Pubblicazione: (2025)

Computability of Initial Value Problems
di: Brattka, Vasco, et al.
Pubblicazione: (2024)

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

A proof complexity conjecture and the Incompleteness theorem
di: Krajicek, Jan
Pubblicazione: (2023)

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

Failure of the strong feasible disjunction property
di: Krajicek, Jan
Pubblicazione: (2026)

Algebra of Self-Replication
di: Moss, Lawrence S.
Pubblicazione: (2023)

Arithmetics within the Linear Time Hierarchy
di: Pollett, Chris
Pubblicazione: (2025)

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

The Serial Scaling Hypothesis
di: Liu, Yuxi, et al.
Pubblicazione: (2025)

Probabilistic Nets-within-Nets
di: Köhler-Bußmeier, Michael
Pubblicazione: (2024)

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

On the relative asymptotic expressivity of inference frameworks
di: Koponen, Vera, et al.
Pubblicazione: (2022)

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
di: Lopez, Aliaume
Pubblicazione: (2024)

The equational theory of the Weihrauch lattice with (iterated) composition
di: Pradic, Cécilia
Pubblicazione: (2024)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
di: Böhnlein, Toni, et al.
Pubblicazione: (2024)

Simulating and model checking membrane systems using strategies in Maude
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

Computing Distinguishing Formulae for Threshold-Based Behavioural Distances
di: Forster, Jonas, et al.
Pubblicazione: (2026)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
di: Alpay, Faruk, et al.
Pubblicazione: (2026)

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

The Orientation Boundary for Step-Duplicating Recursors: Mechanized Impossibility, Escape, and Certification
di: Rahnama, Moses
Pubblicazione: (2025)

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

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

Finitely (In)tractable Promise Constraint Satisfaction Problems
di: Asimi, Kristina, et al.
Pubblicazione: (2020)

Graded Monad Coalgebras for Continuous-Time Transition Systems
di: Di Lavore, Elena, et al.
Pubblicazione: (2026)

Strategies, model checking and branching-time properties in Maude
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

Model checking strategy-controlled systems in rewriting logic
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

Metalevel transformation of strategies
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

The Complexity of Iterated Reversible Computation
di: Eppstein, David
Pubblicazione: (2021)