Link crossing number problem is NP-hard.
problem Determining the crossing number of a link.
method NP-hardness proof.
result Link crossing number problem is NP-hard.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,051 papers · 148 categories
Trend · papers per month
48 results for “NP Hard Problem”
Moving between 3-manifold triangulations is NP-hard
problem Moving between two triangulations of a 3-manifold
method Showing that the number of bistellar moves and sparse degree-two edge collapses is NP-hard
result First NP-hardness result concerning moves between two triangulations of a 3-manifold
Shellability is NP-completemath.CO
We prove that for every , deciding if a pure, -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every and , deciding if a pure, -dimensional, simplicial com…
Trading system uses NP-hard optimization to select stocks for high Sharpe ratio trading.
problem Finding profitable, uncorrelated stocks for high Sharpe ratio trading.
method NP-hard combinatorial optimization using Ising machine and simulated bifurcation algorithm.
result Trading strategy with FPGA-based system achieves 164 μs response latency.
We show that {\sc Heegaard Genus }, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to , is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem {\sc CNF-SAT} to {\sc Heegaard Genus }.
Proving NP-hardness of unknotting and related link problems.
problem Determining if a knot can be untangled with a limited number of moves.
method Proving NP-hardness through reductions to known hard problems.
result Several link problems are proven to be NP-hard.
Deep learning synthesizes diverse solutions for NP-hard problems.
problem Finding optimal solutions for NP-hard problems.
method Graph convolutional network trained to estimate solution likelihood; guided tree search.
result Substantial performance improvement over recent deep learning work.
We prove that certain problems naturally arising in knot theory are NP--hard or NP--complete. These are the problems of obtaining one diagram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number , finding a -component unlink as a sub…
Embeddability in is NP-hardmath.GT
We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an filling is NP-hard. The former stands in contrast with the lower dimensional cases wh…
Paper introduces scalable neural architecture for solving NP-hard problems.
problem Solving NP-hard reasoning problems from natural inputs.
method Scalable neural architecture and loss function for discrete Graphical Models.
result Empirically shows efficient learning of NP-hard problems.
Bailouts in financial networks are hard to optimize due to NP-hardness.
problem Optimizing bailouts in a network of insolvent banks.
method Modeling bailouts as an optimization problem, proving NP-hardness and inapproximability.
result Banks can strategically alter debt contracts to increase their market value in the event of a bailout.
Two DRL policies collaborate to solve NP-hard routing problems.
problem Solving complex routing problems like TSP without expert knowledge.
method Learning Collaborative Policies (LCP) using seeder and reviser policies.
result Improves solution quality over single-policy DRL on various NP-hard routing problems.
It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in test…
Optimal CL requires perfect memory and is NP-hard.
problem Designing CL algorithms that perform reliably and avoid catastrophic forgetting.
method Theoretical approach to derive computational properties of optimal CL algorithms.
result Optimal CL algorithms generally solve an NP-hard problem and require perfect memory.
We show that three natural decision problems about links and 3-manifolds are computationally hard, assuming some conjectures in complexity theory. The first problem is determining whether a link in the 3-sphere bounds a Seifert surface with Thurston norm at most a given integer; this is shown to be NP-complete. The sec…
Researchers prove NP-hardness of learning parameter-bounded Bayes nets.
problem Learning parameter-bounded Bayes nets is computationally hard.
method Proved NP-hardness of learning parameter-bounded Bayes nets and a promise search variant.
result Proved NP-hardness of a promise search variant of LEARN.
Hardness result for approximating manifold radius.
problem Approximating the radius of triangulated manifolds.
method Proving NP-hardness for almost-polynomial approximation.
result It is NP-hard to approximate the hyperspherical radius up to an almost-polynomial factor.
New method improves solving NP-hard problems on graphs.
problem Solving combinatorial optimization problems on graphs.
method A novel reinforcement learning strategy based on AlphaGo Zero for graph embeddings.
result Our method generalizes better to various graphs than S2V-DQN.
New research shows deep learning struggles with hard problems due to biased data generation.
problem Deep learning's limitations in solving computationally hard problems.
method Proved that polynomial-time sample generators for NP-hard problems sample from easier sub-problems.
result Machine learning models trained on biased datasets overestimate their accuracy for hard problems.
New proof shows a link problem is hard without complex links.
problem Deciding if a link contains a trivial sublink is hard.
method Reduces from Independent Set Problem, avoiding Brunnian links.
result The Trivial Sublink Problem is NP-hard due to mod 2 linking.
Paper tackles NP-hard multi-agent planning with reinforcement learning.
problem Solving NP-hard multi-agent, multi-task planning problems with time-dependent rewards.
method Developed a reinforcement learning framework using mean-field inference and auction-based selection.
result Achieved near-optimality and transferability in solving MRRC and IPMS problems.
Study shows optimal RL with transition look-ahead is NP-hard for .
problem Optimal reinforcement learning with transition look-ahead is computationally hard.
method Proved NP-hardness for using linear programming.
result There is a precise boundary between tractable and intractable cases for RL with look-ahead.
The paper proves shellability is hard for d-balls when d is at least 3.
problem Shellability for d-balls is NP-hard when d ≥ 3.
method NP-hardness proof for triangulated d-balls and d-manifolds/d-pseudomanifolds with boundary.
result Shellability is NP-hard for triangulated d-balls when d ≥ 3.
Equity-Transformer solves NP-hard min-max routing problems efficiently.
problem Min-max routing problems with multiple agents and large-scale applications.
method Sequential planning approach with Transformer and equitable workload distribution inductive biases.
result Significant runtime and cost reductions in min-max mTSP and min-max mPDP tasks.
We give a reduction from {\sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.
Training neural networks is hard in fixed dimensions.
problem Training two-layer neural networks is computationally hard in fixed dimensions.
method Parameterized complexity analysis considering dimension and number of neurons.
result Training two-layer neural networks is NP-hard for two dimensions.
Sparse linear regression is hard to solve efficiently, even with k-sparse solutions.
problem Sparse linear regression problem with k-sparse solutions.
method Fine-grained complexity and hardness assumptions.
result No better-than-brute-force algorithms exist for sparse linear regression.
GSO framework optimizes COPs on graphs using Gumbel-softmax.
problem Finding optimal configurations or network structures in combinatorial optimization problems.
method Introducing Gumbel-softmax technique for direct optimization of objective functions.
result High-quality solutions obtained with less time compared to traditional methods.
Computing PL geometric category in 2D is NP-hard.
problem Determining the PL geometric category of 2D polyhedra.
method Reduction from shellability of 2-complexes, which is known to be NP-hard.
result It is NP-hard to decide whether the PL geometric category of a 2D polyhedron is at most 2.
Ergodic Annealingcs.AI
New method uses reinforcement learning to improve Simulated Annealing.
problem Optimization problems with unknown cost functions.
method Replaces Metropolis engine with Macau Algorithm.
result Effective heuristic for unknown cost functions.
We investigate the complexity of finding an embedded non-orientable surface of Euler genus in a triangulated -manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into -manifolds. We prove that the problem is NP…
In this thesis I explore challenging discrete energy minimization problems that arise mainly in the context of computer vision tasks. This work motivates the use of such "hard-to-optimize" non-submodular functionals, and proposes methods and algorithms to cope with the NP-hardness of their optimization. Consequently, t…
Hardness proven for embedding simplicial complexes in R^d, especially for k-dimensional ones.
problem Recognizing almost embeddability of k-dimensional complexes in R^d.
method NP-hardness proof using configuration spaces and preimage cycle properties.
result Embedding obstruction is incomplete for k-dimensional complexes in R^d.
Study on computing and estimating calibration distance, showing hardness and efficiency.
problem Computing and estimating calibration distance under different assumptions.
method Efficient algorithm for exact computation, polynomial-time approximation scheme; sample-based estimation for upper bounds.
result The problem becomes NP-hard when assumptions are removed, but efficient algorithms exist under certain conditions.
Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxationcs.LG
Paper solves NP-hard sparse mixed linear regression problem with provable guarantees.
problem Sparse mixed linear regression on unlabeled data.
method Invex relaxation for intractable problem with theoretical guarantees.
result Exact recovery of data labels and close approximation of regression parameters.
Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphscs.LG
A new algorithm optimizes graph problems faster and more accurately.
problem Hard optimization problems on graphs.
method Gumbel-softmax technique with gradient descent and evolution strategy.
result High-quality solutions obtained with less time.
Paper tackles P vs NP problem in portfolio optimization with cardinality constraints and Black-Scholes derivatives.
problem Operationalizing the P vs NP problem in cardinality-constrained portfolio selection.
method Mixed-integer quadratic program with genetic algorithms, Monte Carlo sampling, and greedy screening.
result Cardinality constraint reshapes efficient frontier, highlighting trade-offs between stability and computational cost.
Boolean logic used for neural network training and inference, with convergence analysis.
problem Discrete optimization in neural networks with Boolean logic.
method Boolean logic backpropagation with convergence analysis.
result First convergence analysis for Boolean logic in neural networks.
EPMF factorizes matrices by adjusting their entries to match a specified power.
problem Factorizing matrices with adjusted entries to match a specified power.
method Analyzes the computational complexity of exact and approximate EPMF problems.
result Exact EPMF is strongly NP-hard, but can be solved in polynomial time when rank is fixed.
New MIP formulations for neural network Lipschitz constant estimation.
problem Ensuring robustness of neural networks by calculating their Lipschitz constant.
method Reformulating the neural network Lipschitz estimation problem as a Quadratically Constrained MIP (MIQCQP) problem.
result Solutions of the MIQCQP formulations provide bounds on the Lipschitz constant, with conditions for exactness.
D-Wave computers struggle with sampling Boltzmann distributions efficiently.
problem Sampling Boltzmann distributions efficiently on D-Wave computers.
method Exploring various obstacles and remaining difficulties.
result Challenges remain in using D-Wave computers for efficient sampling.
We investigate the computational complexity of some problems in three-dimensional topology and geometry. We show that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. Using similar ideas, we show that deciding whether a curve in a metrized PL 3-manifold bounds a surface of area…
Several learning applications require solving high-dimensional regression problems where the relevant features belong to a small number of (overlapping) groups. For very large datasets and under standard sparsity constraints, hard thresholding methods have proven to be extremely efficient, but such methods require NP h…
Market competition depends on computational complexity, P != NP makes it impossible.
problem Competitive market outcomes require computational intractability.
method Analyzes the computational hardness of collusion detection in markets.
result If P != NP, collusion detection is computationally infeasible, making collusion unstable.
Efficient algorithm solves best subset selection problem.
problem Sparse learning problems, especially best subset selection.
method Primal-dual method based on dual forms of -regularized problems.
result Improves solutions of best subset selection with reduced redundant computation.
A framework explains neural network decisions using rate-distortion theory.
problem Interpreting neural network decisions as an optimisation problem.
method Rate-distortion framework, NP-hard problem, heuristic solution strategy.
result The problem is NP-hard and NP-complete, making it computationally challenging.
Transformers struggle to learn Markovian dynamics, showing NP-hard optimization challenges.
problem Understanding transformers' limitations in learning Markovian dynamical functions.
method Investigated through a structured ICL setup, analyzing loss landscapes and parameter optimization.
result Recovering optimal transformer parameters for Markovian functions is NP-hard.
Proposes a self-paced multi-label learning method to handle diverse labels efficiently.
problem Learning from multi-label data with a large label space is NP-hard and prone to overfitting.
method Self-paced multi-label learning with diversity (SPMLD) approach, incorporating gradual label inclusion and diversity maintenance.
result The proposed SPMLD framework optimizes a non-convex objective function using block coordinate descent.