How Hard is it to be a Star? Convex Geometry and the Real Hierarchy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schaefer, Marcus, Štefankovič, Daniel
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry Computational Complexity 68Q17, 52-08
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
by: Lubiw, Anna, et al.
Published: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Eight-Partitioning Points in 3D, and Efficiently Too
by: Aronov, Boris, et al.
Published: (2024)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Recent Advances in Debordering Methods
by: Dutta, Pranjal, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
by: Meijer, Lucas, et al.
Published: (2026)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
by: Chan, Swee Hong, et al.
Published: (2023)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Complexity of Sequence-to-Graph Alignment with Co-Linear Chaining
by: Li, Xingfu
Published: (2026)

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
by: Ye, Yuhan
Published: (2026)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Border subrank via a generalised Hilbert-Mumford criterion
by: Biaggi, Benjamin, et al.
Published: (2024)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Exact values of generic subrank
by: Pielasa, Paweł, et al.
Published: (2024)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
by: Li, Xingfu, et al.
Published: (2026)

Complexity of chess domination problems
by: Langlois-Rémillard, Alexis, et al.
Published: (2022)

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

Quantum Lower Bounds by Sample-to-Query Lifting
by: Wang, Qisheng, et al.
Published: (2023)

Flexible constraint satisfiability and a problem in semigroup theory
by: Jackson, Marcel
Published: (2015)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

On the complexity of solving equations over the symmetric group $S_4$
by: Aichinger, Erhard, et al.
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Recognition of Seifert fibered spaces with boundary is in NP
by: Jackson, Adele
Published: (2023)