Results 11 to 20 of about 35,538 (168)
INFLATING BALLS IS NP-HARD [PDF]
International Journal of Computational Geometry & Applications, 2011 A collection [Formula: see text] of balls in ℝd is δ-inflatable if it is isometric to the intersection [Formula: see text] of some d-dimensional affine subspace E with a collection [Formula: see text] of (d + δ)-dimensional balls that are disjoint and have equal radius.
Batog, Guillaume, Goaoc, Xavier
openaire +3 more sources
The Moving Firefighter Problem
Mathematics, 2022 The original formulation of the firefighter problem defines a discrete-time process where a fire starts at a designated subset of the vertices of a graph G.
Bruno R. Gutiérrez-De-La-Paz +5 more
doaj +1 more source
, 2022 Wordle is a single-player word-guessing game where the goal is to discover a secret word $w$ that has been chosen from a dictionary $D$. In order to discover $w$, the player can make at most $\ell$ guesses, which must also be words from $D$, all words in $D$ having the same length $k$.
Lokshtanov, Daniel +1 more
openaire +4 more sources
Protein Design is NP-hard [PDF]
Protein Engineering, Design and Selection, 2002 Biologists working in the area of computational protein design have never doubted the seriousness of the algorithmic challenges that face them in attempting in silico sequence selection. It turns out that in the language of the computer science community, this discrete optimization problem is NP-hard. The purpose of this paper is to explain the context
Pierce, Niles A., Winfree, Erik
openaire +3 more sources
NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
Frontiers in Quantum Science and Technology, 2023 In the last decade, public and industrial research funding has moved quantum computing from the early promises of Shor’s algorithm through experiments to the era of noisy intermediate scale quantum devices (NISQ) for solving real-world problems.
Rhonda Au-Yeung +2 more
doaj +1 more source
Terrain Guarding is NP-Hard [PDF]
SIAM Journal on Computing, 2010 Summary: A set \(G\) of points on a terrain, also known as an \(x\)-monotone polygonal chain, is said to guard the terrain if every point on the terrain is seen by a point in \(G\). Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain.
King, James, Krohn, Erik
openaire +3 more sources
The Burning Number of Directed Graphs: Bounds and Computational Complexity
Theory and Applications of Graphs, 2020 The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs,
Remie Janssen
doaj +1 more source
Operating Room Scheduling by Using Hybrid Genetic Algorithm
Düzce Üniversitesi Bilim ve Teknoloji Dergisi, 2022 Hospitals are among the most important institutions of today. For hospitals, efficient use of operating rooms is of great importance. Efficient use of operating rooms is a problem that needs to be solved.
Tunahan Timuçin, Serdar Biroğul
doaj +1 more source
Training Variational Quantum Algorithms Is NP-Hard [PDF]
Physical Review Letters, 2021 Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum ap- proximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively.
Lennart Bittel, Martin Kliesch
openaire +3 more sources
The computational complexity of the gear placement problem
Journal of Advanced Mechanical Design, Systems, and Manufacturing, 2020 In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed.
Vitor Mitsuo FUKUSHIGUE HAMA +5 more
doaj +1 more source