Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Yamakami, Tomoyuki
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

A Schematic Definition of Quantum Polynomial Time Computability
por: Yamakami, Tomoyuki
Publicado: (2018)

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

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

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

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

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

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

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

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

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

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

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

Monotone Contractions
por: Batziou, Eleni, et al.
Publicado: (2024)

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

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

Monotone Circuit Complexity of Matching
por: Cavalar, Bruno, et al.
Publicado: (2025)

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

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

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

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

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

Maximizing Minimum Cycle Bases Intersection
por: Watel, Dimitri, et al.
Publicado: (2024)

A Distance Amplification Lemma for Monotonicity
por: Minzer, Dor
Publicado: (2025)

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

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

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

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

Maximal Line Digraphs
por: Japhet, Quentin, et al.
Publicado: (2024)

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

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

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

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

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

Maximization of Approximately Submodular Functions
por: Horel, Thibaut, et al.
Publicado: (2024)

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

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

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