Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProjection onto the Cosparse Set is NP-Hard
171
0
0.0
(
0
)
Added by
Remi Gribonval
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The computational complexity of a problem arising in the context of sparse optimization is considered, namely, the projection onto the set of $k$-cosparse vectors w.r.t. some given matrix $Omeg$. It is shown that this projection problem is (strongly) NP-hard, even in the special cases in which the matrix $Omeg$ contains only ternary or bipolar coefficients. Interestingly, this is in contrast to the projection onto the set of $k$-sparse vectors, which is trivially solved by keeping only the $k$ largest coefficients.
rate research
Read More
We prove that deciding whether the Runner can win this turn (mate-in-1) in the Netrunner card game generalized to allow decks to contain an arbitrary number of copies of a card is weakly NP-hard. We also prove that deciding whether the Corp can win within two turns (mate-in-2) in this generalized Netrunner is weakly NP-hard.
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open problems posed over 15 years ago [BDH+04]. Our reduction is from 3-Partition, similar to the previous reduction for unrestricted board sizes, but with a better packing of buckets. On the positive side, we prove that 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that the generalization of Tetris to larger $k$-omino pieces is NP-complete even when the board starts empty, even when restricted to 3 columns or 2 rows or constant-size pieces. Finally, we present an animated Tetris font.
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer horizontally than vertically, rectangles containing | are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.
211 -
Adrien Friggeri
, Eric Fleury (ENS / LIPn Laboratoire de lInformatique du Parallelisme / INRIA Grenoblen Rh^one-Alpes
2011
We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
In this paper, we show that deciding rigid foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from Partition, and that deciding rigid foldability with optional creases is strongly NP-hard by a reduction from 1-in-3 SAT. Unlike flat foldability of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldability from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matter and reconfigurable robots.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
