1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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)