Skip to main content
Code Golf

Return to Answer

added 37 characters in body
Source Link
Sanchises
Sanchises
  • 9.5k
  • 14
  • 13

Answers should surely give a correct result within finite time.

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • While a program could give an answer with probability of 1 ('almost surely'), the expected runtime is then arbitrarily long (possibly even infinite).
  • Interesting challenges could be trivialized; for example, when verifying the correct solution out of randomly generated candidates is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Answers should surely give a correct result within finite time.

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • While a program could give an answer with probability of 1 ('almost surely'), the expected runtime is then arbitrarily long (possibly even infinite).
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Answers should surely give a correct result within finite time.

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • While a program could give an answer with probability of 1 ('almost surely'), the expected runtime is then arbitrarily long (possibly even infinite).
  • Interesting challenges could be trivialized; for example, when verifying the correct solution out of randomly generated candidates is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

"Arbitrary time bound" is open to misintepretation for those unfamiliar with the mathematical meaning of "arbitrary".
Source Link
Sanchises
Sanchises
  • 9.5k
  • 14
  • 13

Answers should surely give a correct result within some arbitrary finite time bound.

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • We often expect programs to run within reasonable time, where the definition on 'reasonable' depends on the problem. While a program could give an answer with probability of 1 ('almost surely'), the expected runtime is then arbitrarily long (possibly even infinite).
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Answers should surely give a correct result within some arbitrary finite time bound

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • We often expect programs to run within reasonable time, where the definition on 'reasonable' depends on the problem. While a program could give an answer with probability of 1, the expected runtime is then arbitrarily long (possibly even infinite.
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Answers should surely give a correct result within finite time.

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • While a program could give an answer with probability of 1 ('almost surely'), the expected runtime is then arbitrarily long (possibly even infinite).
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Clarify that this answer requires a finite time bound
Source Link
ymbirtt
ymbirtt
  • 1.9k
  • 9
  • 5

Answers should surely give a correct result within some arbitrary finite time bound

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • We often expect programs to run within reasonable time, where the definition on 'reasonable' depends on the problem. While a program could give an answer with probability of 1, the expected runtime is then arbitrarily long (possibly even infinite.
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Answers should surely give a correct result

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • We often expect programs to run within reasonable time, where the definition on 'reasonable' depends on the problem. While a program could give an answer with probability of 1, the expected runtime is then arbitrarily long (possibly even infinite.
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

Answers should surely give a correct result within some arbitrary finite time bound

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • We often expect programs to run within reasonable time, where the definition on 'reasonable' depends on the problem. While a program could give an answer with probability of 1, the expected runtime is then arbitrarily long (possibly even infinite.
  • Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

added 74 characters in body
Source Link
Sanchises
Sanchises
  • 9.5k
  • 14
  • 13
Source Link
Sanchises
Sanchises
  • 9.5k
  • 14
  • 13