3 votes

Is there a conditional lower bound for the k max subarray sum problem?

In "Computing Maximum-Scoring Segments Optimally" by Fredrik Bengtsson & Jingsen Chen the authors describe an $O(n)$ algorithm.
orlp's user avatar
  • 825
3 votes

How can I show a Gap-P problem is outside #P

This area has grown immensely in the 12 years since I asked the question. In particular, Ikenmeyer, Pak and Panova have shown that the squares of symmetric group characters are not in #(P), unless the ...
David E Speyer's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible