Skip to main content
Puzzling

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

11
  • 9
    $\begingroup$ Good ol' rock, nothing beats that! $\endgroup$ Commented Sep 14 at 18:07
  • 2
    $\begingroup$ Does it have to be a deterministic algorithm, or can it be randomised? For example, can they use coin tosses as part of their strategy? $\endgroup$ Commented Sep 14 at 23:21
  • 2
    $\begingroup$ @Pranay The best random strategy cannot do better than the best deterministic strategy. This is not always true if quantum strategies are allowed. $\endgroup$ Commented Sep 15 at 23:07
  • 1
    $\begingroup$ @Lucenaposition. In general, BPP vs P isn’t settled, right? Are you talking about this particular problem? If so, is it easy to see why randomisation doesn’t give better strategies in this problem? $\endgroup$ Commented Sep 15 at 23:20
  • 2
    $\begingroup$ @Pranay Randomisation is like a "local hidden variable" while quantum is like "non-local hidden variable". (I assume the hats are chosen by chance, not by an opponent who knows their strategy) If the opponent knows the strategy and can choose, randomisation can be useful. $\endgroup$ Commented Sep 15 at 23:30