Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/#!/StackCSTheory/status/132054369960067072
added 274 characters in body
Source Link
arnab
arnab
  • 7k
  • 1
  • 39
  • 55

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?

EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are many possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness. I realize that the question is probably not fully specified...

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?

EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are many possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness. I realize that the question is probably not fully specified...

added 10 characters in body
Source Link
arnab
arnab
  • 7k
  • 1
  • 39
  • 55

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?

Source Link
arnab
arnab
  • 7k
  • 1
  • 39
  • 55

Randomized algorithm that "looks" deterministic?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem. But is there an algorithm of the above kind whose expected running time is intermediate between the two?