Imagen de Portada

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bannach, Max, Demaine, Erik D., Gomez, Timothy, Hecher, Markus
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science Combinatorics 68Q17, 68Q15, 68Q25, 68Q27, 03B05, 03D10, 03D15, 05C85, 05C62, 05-08, 94C15 G.2.1; G.2.2; F.4.1; F.1.3; F.1.1
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma
por: Mourad, Daniel
Publicado: (2024)

NP-hard problems are not in BQP
por: Czerwinski, Reiner
Publicado: (2023)

Degree-preserving graph dynamics -- a versatile process to construct random networks
por: Erdős, Péter L., et al.
Publicado: (2021)

The Gallai Vertex Problem is $Θ_2^p$-Complete
por: Nikabadi, Amir, et al.
Publicado: (2026)

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

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
por: Golovach, Petr A., et al.
Publicado: (2022)

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

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

Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame Approach
por: Riis, Søren
Publicado: (2024)

Why the classes P and NP are not well-defined finitarily
por: Anand, Bhupinder Singh
Publicado: (2024)

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

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

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

Dichotomy for orderings?
por: Kun, Gábor, et al.
Publicado: (2025)

Graded Monads in the Semantics of Nominal Automata
por: Schulze, Hannes, et al.
Publicado: (2025)

Separation of PSPACE and EXP
por: Czerwinski, Reiner
Publicado: (2021)

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

An arithmetic method algorithm optimizing k-nearest neighbors compared to regression algorithms and evaluated on real world data sources
por: Anagnostopoulos, Theodoros, et al.
Publicado: (2026)

Lindenmayer graph languages, first-order theories and expanders
por: Knapik, Teodor
Publicado: (2024)

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

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

The Optimizer Quotient and the Certification Trilemma
por: Simas, Tristan
Publicado: (2026)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
por: Emmerich, Michael T. M., et al.
Publicado: (2026)

Formal Probabilistic Methods for Combinatorial Structures using the Lovász Local Lemma
por: Edmonds, Chelsea, et al.
Publicado: (2023)

The Polynomial Hierarchy does not collapse
por: Czerwinski, Reiner
Publicado: (2024)

Results on three problems on isolation of graphs
por: Borg, Peter, et al.
Publicado: (2026)

DAG Scheduling in the BSP Model
por: Papp, Pál András, et al.
Publicado: (2023)

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

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

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
por: Abdullah, Duaa, et al.
Publicado: (2025)

Truth-Aware Decoding: A Program-Logic Approach to Factual Language Generation
por: Alpay, Faruk, et al.
Publicado: (2025)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
por: Oliveria, Mateus de Oliveira, et al.
Publicado: (2026)

Exploring P versus NP
por: Tang, Jian-Gang
Publicado: (2022)

Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies
por: Riis, Søren
Publicado: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
por: Philip, Geevarghese, et al.
Publicado: (2026)

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

Unifying Weak Independence and Signal Hierarchy Theory: Extended Biological Petri Net Formalism with Application to Vibrio fischeri Quorum Sensing
por: Simao, Eugenio
Publicado: (2025)

Graph polynomials: some questions on the edge
por: Farr, Graham, et al.
Publicado: (2024)

Understanding and Improving Automated Proof Synthesis for Interactive Theorem Provers
por: Zhang, Manqing, et al.
Publicado: (2026)

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