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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook