StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POEstimating difficulty of instances of NP problems
text
Body
copied!<p>NP problems look like they are suitable for use as trapdoor functions or proofs of work, since they are difficult to solve, but easy to verify. Unfortunately, they seem a little hard to use in adversarial settings where an opponent can control problem selection because while worst-case problems are NP, particular instances can be solved very quickly.</p> <p>So: is there any algorithm which can take instances and estimate - more efficiently than trying to solve them - how hard or close to worst-case they are?</p> <p>(The context is musing about a Bitcoin protocol where the proofs-of-work were reusable and not useless hash checks. The obvious approach is to have a central authority issue, for each transaction block, a NP instance which corresponds to a real-world problem. But the central authority could be subverted, and start issuing easy problems which would render the network vulnerable to double-spends. One could accept problems from multiple authorities, or anyone, but the chosen-easy problem remains. If there were some way to <em>estimate</em> the difficulty of any problem presented to the network, then 'too easy' problems could simply be ignored, falling back to the hash race if necessary.)</p> <p>EDIT: jaxtr links me to <a href="http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf" rel="nofollow" title="Xu et al 2012">"Predicting Satisfiability at the Phase Transition"</a>, which gives algorithms which estimate hardness at 70% accuracy - but they don't seem to investigate whether the algorithm can be deliberately fooled. (As well, one can apparently generate SAT problems with specified probabilities of being satisfiable.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload