Imagen de Portada

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP

Fuente: arXiv

Guardado en:

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

Ejemplares similares

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
por: Çivril, Ali
Publicado: (2021)

Scheme-Theoretic Approach to Computational Complexity. III. SETH
por: Çivril, Ali
Publicado: (2023)

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
por: Çivril, Ali
Publicado: (2023)

P=NP
por: Deng, Zikang
Publicado: (2024)

P vs. NP
por: Uribe, Daniel
Publicado: (2016)

On P Versus NP
por: Gordeev, Lev
Publicado: (2020)

Communication Complexity is NP-hard
por: Hirahara, Shuichi, et al.
Publicado: (2025)

A Critique of Deng's "P=NP"
por: Humphreys, Isabel, et al.
Publicado: (2025)

Some conditions implying if P=NP then P=PSPACE
por: Rodriguez, Ismael
Publicado: (2026)

The Separation of $NP$ and $PSPACE$
por: Lin, Tianrong
Publicado: (2021)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
por: Asadi, Ali, et al.
Publicado: (2024)

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
por: Meng, Boning, et al.
Publicado: (2025)

Topological Collapse: P = NP Implies #P = FP via Solution-Space Homology
por: Alasli, M.
Publicado: (2026)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
por: Kayibi, Koko-Kalambay Kalafan
Publicado: (2018)

Computational Complexity of Game Boy Games
por: Tirmazi, Hayder, et al.
Publicado: (2024)

Separations in Proof Complexity and TFNP
por: Göös, Mika, et al.
Publicado: (2022)

Wataridori is NP-Complete
por: Ruangwises, Suthee
Publicado: (2026)

Nondango is NP-Complete
por: Ruangwises, Suthee
Publicado: (2023)

Computing the EHZ capacity is NP-hard
por: Leipold, Karla, et al.
Publicado: (2024)

Proofs of NP = coNP = PSPACE: Current upgrade
por: Gordeev, Lev, et al.
Publicado: (2023)

On $NP \cap coNP$ proof complexity generators
por: Krajicek, Jan
Publicado: (2025)

A proof of P!=NP
por: McCallum, Rupert
Publicado: (2020)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
por: DeJesse, Nicholas, et al.
Publicado: (2025)

BusOut is NP-complete
por: Ishibashi, Takehiro, et al.
Publicado: (2025)

On Kernelization with Access to NP-Oracles
por: Molter, Hendrik, et al.
Publicado: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
por: Nederlof, Jesper
Publicado: (2026)

Symport/Antiport P Systems with Membrane Separation Characterize P^(#P)
por: Ducros, Vivien, et al.
Publicado: (2025)

NP-Completeness of Neighborhood Balanced Colorings
por: Asaeedi, Saeed
Publicado: (2024)

The 2-Attractor Problem is NP-Complete
por: Fuchs, Janosch, et al.
Publicado: (2023)

An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich)
por: Alasli, M.
Publicado: (2025)

NP-Completeness of Multicast Beamforming in Wireless Communication
por: Shrestha, Sagar
Publicado: (2025)

Additive Models Explained: A Computational Complexity Approach
por: Bassan, Shahaf, et al.
Publicado: (2025)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
por: Romão, Leonardo Gasparini, et al.
Publicado: (2025)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
por: Martinsson, Björn
Publicado: (2024)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
por: Gaspers, Serge, et al.
Publicado: (2025)

The Radical Solution and Computational Complexity
por: Zheng, Bojin, et al.
Publicado: (2024)

The Computational Complexity of Factored Graphs
por: Gupta, Shreya, et al.
Publicado: (2024)

Random Permutations in Computational Complexity
por: Hitchcock, John M., et al.
Publicado: (2025)

Computational-Statistical Tradeoffs from NP-hardness
por: Blanc, Guy, et al.
Publicado: (2025)

Limits of structures and Total NP Search Problems
por: Ježil, Ondřej
Publicado: (2023)