np-hard
A classification for problems for which no known polynomial-time algorithm can guarantee a solution. In the context of AI, many optimization and search problems fall into this category, indicating their computational intractability.
- $\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
- A Partition Cover Approach to Tokenization
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing
- Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
- Graph Alignment via Birkhoff Relaxation
- Memory-Enhanced Neural Solvers for Routing Problems
- Non-rectangular Robust MDPs with Normed Uncertainty Sets
- On the Hardness of Approximating Distributions with Tractable Probabilistic Models
- Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
- PointTruss: K-Truss for Point Cloud Registration
- SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
- The Complexity of Correlated Equilibria in Generalized Games
- The Complexity of Finding Local Optima in Contrastive Learning
- Top-H Decoding: Adapting the Creativity and Coherence with Bounded Entropy in Text Generation
- Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms