
PreviousNext
We show that the minimum distance of a linear code (or
equivalently, the weight of the lightest codeword) is
not approximable to within any constant factor in random polynomial
time (RP), unless NP equals RP.
Under the stronger assumption that NP is not contained in RQP
(random ...
more >>>
Dutton presents a further HEAPSORT variant called
WEAK-HEAPSORT which also contains a new data structure for
priority queues. The sorting algorithm and the underlying
data structure ara analyzed showing that WEAK-HEAPSORT is
the best HEAPSORT variant and that it has a lot of nice
more >>>
We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open
problems about sparse polynomials.
PreviousNext