Copertina

Sorting by Strip Swaps is NP-Hard

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Roy, Swapnoneel, Asaithambi, Asai, Mukhopadhyay, Debajyoti
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Artificial Intelligence Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Improved Hardness-of-Approximation for Token Swapping
di: Hiken, Sam, et al.
Pubblicazione: (2024)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2025)

Improving Merge Sort and Quick Sort Performance by Utilizing Alphadev's Sorting Networks as Base Cases
di: Aly, Anas Gamal, et al.
Pubblicazione: (2025)

TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
di: Amini, Amin
Pubblicazione: (2024)

String Consensus Problems with Swaps and Substitutions
di: Gabory, Estéban, et al.
Pubblicazione: (2025)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
di: Sato, Atsuki, et al.
Pubblicazione: (2024)

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

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

Avoiding Obfuscation with Prover-Estimator Debate
di: Brown-Cohen, Jonah, et al.
Pubblicazione: (2025)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
di: Banik, Aritra, et al.
Pubblicazione: (2025)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
di: Nye, Logan
Pubblicazione: (2025)

Deciding if a DAG is Interesting is Hard
di: De Carufel, Jean-Lou, et al.
Pubblicazione: (2025)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
di: Arvind, V., et al.
Pubblicazione: (2023)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

Hardness of Dynamic Core and Truss Decompositions
di: Couto, Yan S., et al.
Pubblicazione: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

Sampling Permutations with Cell Probes is Hard
di: Alekseev, Yaroslav, et al.
Pubblicazione: (2025)

k-SUM Hardness Implies Treewidth-SETH
di: Lampis, Michael
Pubblicazione: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
di: Reddy, Sangam Balchandar
Pubblicazione: (2025)

Sumplete is Hard, Even with Two Different Numbers
di: Ruangwises, Suthee
Pubblicazione: (2023)

Hardness Results on Characteristics for Elastic-Degenerated Strings
di: Köppl, Dominik, et al.
Pubblicazione: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
di: Gadekar, Ameet, et al.
Pubblicazione: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2026)

Training Neural Networks is NP-Hard in Fixed Dimension
di: Froese, Vincent, et al.
Pubblicazione: (2023)

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

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
di: Adriaens, Florian, et al.
Pubblicazione: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Recognizing Sumsets is NP-Complete
di: Abboud, Amir, et al.
Pubblicazione: (2024)

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

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

Compression Barriers for Autoregressive Transformers
di: Haris, Themistoklis, et al.
Pubblicazione: (2025)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
di: Blum, Avrim, et al.
Pubblicazione: (2025)

Theoretical limitations of multi-layer Transformer
di: Chen, Lijie, et al.
Pubblicazione: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
di: Thejaswi, Suhas, et al.
Pubblicazione: (2024)

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
di: Feng, Guhao, et al.
Pubblicazione: (2023)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
di: Huang, Neng, et al.
Pubblicazione: (2024)