Cover Image

Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yamakami, Tomoyuki
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
by: Yamakami, Tomoyuki
Published: (2025)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
by: Yamakami, Tomoyuki
Published: (2022)

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
by: Yamakami, Tomoyuki
Published: (2021)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
by: Yamakami, Tomoyuki
Published: (2019)

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
by: Yamakami, Tomoyuki
Published: (2020)

Datalog-Expressibility for Monadic and Guarded Second-Order Logic
by: Bodirsky, Manuel, et al.
Published: (2020)

On the Expressibility of the Reconstructional Color Refinement
by: Arvind, V., et al.
Published: (2024)

Monotone Contractions
by: Batziou, Eleni, et al.
Published: (2024)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
by: Chen, Zhenyu, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
by: Tran, Tan D., et al.
Published: (2025)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
by: Komarath, Balagopal, et al.
Published: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)

Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
by: Jadav, Hareshkumar, et al.
Published: (2026)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
by: Chukhin, Nikolai, et al.
Published: (2024)

Maximizing Minimum Cycle Bases Intersection
by: Watel, Dimitri, et al.
Published: (2024)

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
by: Eagling-Vose, Tala, et al.
Published: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Structural Origin and the Minimal Syntax of NP-Hardness: Analysis of SAT from Syntactic Generativity and Compositional Collapse
by: Nishiyama, Yumiko
Published: (2025)

Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
by: Jones, Mark, et al.
Published: (2024)

Maximal Line Digraphs
by: Japhet, Quentin, et al.
Published: (2024)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
by: Komusiewicz, Christian, et al.
Published: (2024)

Bounded Dynamic Level Maintenance for Efficient Logic Optimization
by: Liu, Junfeng, et al.
Published: (2025)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
by: de Rezende, Susanna F., et al.
Published: (2024)

Quantum Advantage from One-Way Functions
by: Morimae, Tomoyuki, et al.
Published: (2023)

Aspects of Coherence in Dependence Logic
by: Barlag, Timon, et al.
Published: (2026)

Maximization of Approximately Submodular Functions
by: Horel, Thibaut, et al.
Published: (2024)

Logic and Computation through the Lens of Semirings
by: Barlag, Timon, et al.
Published: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

Finite Variable Counting Logics with Restricted Requantification
by: Raßmann, Simon, et al.
Published: (2024)