Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear-time-hard problems wanted

  1. Jan 29, 2014 #1
    Can I have a list of problems suspected of not having linear-time solutions? Like multiplication and sorting.
  2. jcsd
  3. Jan 31, 2014 #2
  4. Jan 31, 2014 #3
    I meant a poly-time problem.
  5. Jan 31, 2014 #4
    Fast Fourier transform (2d or 3d).
    Most trigonometric functions to any specified precision.
    Finding the first "n" primes.
    Defragmenting a disk with "n" fragments.

    Technically, counting to "n" because eventually you would need longer and longer word-lengths.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Linear-time-hard problems wanted
  1. Hard Math Problem (Replies: 5)

  2. Hard Sequence problem (Replies: 4)