All Questions
Tagged with np linear-algebra
3 questions
1
vote
0
answers
118
views
Promise version of minimum distance
It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...
2
votes
1
answer
223
views
Minimal Support Solutions of a Linear System (Dissertation)
For a given $n \times m$ matrix A with $m>>n$ and a given vector $\vec b \in \mathbb{F}^{n \times 1}$, and given that $A\vec{x}=\vec{b}$ for at least one $\vec{x} \in \mathbb{F}^{m \times 1}$, ...
8
votes
4
answers
2k
views
NP-hard problems in linear algebra and real analysis [closed]
I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent.
I would thus like to collect in this thread a list of ...