Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/#!/StackCSTheory/status/597978706083192832
added 118 characters in body
Source Link
Simd
Simd
  • 3.9k
  • 21
  • 49

If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly interested if there are wide gaps for natural problems of general interest.

If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm?

If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly interested if there are wide gaps for natural problems of general interest.

deleted 1 character in body
Source Link
Simd
Simd
  • 3.9k
  • 21
  • 49

If we only consider problems in P, are there any bigsbig gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm?

If we only consider problems in P, are there any bigs gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm?

If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm?

Source Link
Simd
Simd
  • 3.9k
  • 21
  • 49

Big gaps between RAM and Turing machine complexity

If we only consider problems in P, are there any bigs gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm?