bcoburn comments on Open thread, September 2-8, 2013 - Less Wrong

0 Post author: David_Gerard 02 September 2013 02:07PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (376)
Tags: open open_thread

Comments (376)

You are viewing a single comment's thread. Show more comments above.

Comment author: wedrifid 16 September 2013 02:30:51PM 0 points [-]

I am seeking a mathematical construct to use as a logical coin for the purpose of making hypothetical decision theory problems slightly more aesthetically pleasing. The required features are:

  • Unbiased. It gives (or can be truncated or otherwise resolved to give) a 50/50 split on a boolean outcome.
  • Indexable. The coin can be used multiple times through a sequence number. eg. "The n-th digit of pi is even".
  • Intractable. The problem is too hard to solve. Either because there is no polynomial time algorithm to solve it or just because it is somewhat difficult and the 'n' supplied is ridiculous. eg. "The 3^^^3 digit of pi is even".
  • Provable or otherwise verifiable. When the result of the logical coin is revealed it should be possible to also supply a proof of the result that would convince a mathematician that the revealed outcome is correct.
  • Simple to refer to. Either there is a common name for the problem or a link to a description is available. The more well known or straightforward the better.

NP-complete problems have many of the desired features but I don't know off the top of my head any that can be used as indexable fair coin.

Can anyone suggest some candidates?

Comment author: bcoburn 16 September 2013 10:58:14PM 1 point [-]

My first idea is to use something based on cryptography. For example, using the parity of the pre-image of a particular output from a hash function.

That is, the parity of x in this equation:

f(x) = n, where n is your index variable and f is some hash function assumed to be hard to invert.

This does require assuming that the hash function is actually hard, but that both seems reasonable and is at least something that actual humans can't provide a counter example for. It's also relatively very fast to go from x to n, so this scheme is easy to verify.

Comment author: Watercressed 21 September 2013 06:09:08AM -1 points [-]

Hash functions map multiple inputs to the same hash, so you would need to limit the input in some other way, and that makes it harder to verify.

Powered by Reddit Powered by Reddit