3-SAT solution verifiers, and modest extensions to other kinds of problem spaces.

How do you verify 3-SAT? Just plug in the values and check if it evaluates to TRUE? I assume the idea is to pay people to solve NP-hard problems via TX's, which is a kinda neat idea imo.

It's just asking if many 3 term clauses ANDed together are true for a given input set, so you'd give the inputs to spend it to your wallet. Automatic bounties on optimization (sub)problems, yep.

For various reasons, you probably want to use arithmetic and string operations for encoding certain problens. You could do it in bit operations, but efficiency.

I can't take credit for it -- it's one of those things that was floating around as a usage early on, but the features were killed.

Which features? Looks like (arithmetic, not bitwise) AND/OR/NOT are supported, I'm not an expert but it seems like this could be do-able. I'll have to think about this more maybe I'm missing something.