☞ NFTs and NP Problems

The Nature of Beauty meets Proof of Work?

In computer science, there is something known as an NP-complete problem: roughly, for this class of problem, finding the solution to such a problem is considered computationally difficult, but if I were to give you a potential answer, you could nearly instantly respond as to whether it was correct or not. For example, given a whole set of logical formulas, it might be hard to find a set of True/False values that satisfy all of them. But if I gave you a potential solution, you could easily check and see if my answer is the right one.

Inspired by Tony Kulesa, founder of biotech accelerator Petri, I’ve been thinking about NP-completeness recently in the context of NFTs. Tony had been intrigued by Robin Sloan’s amulets: Robin Sloan developed a method for identifying rare snippets of text, specifically ones that had certain properties when run through hash functions. The implication here is that the difficulty of finding rare bits of poetry—ones that have a hash value of four or more 8s in them—could be potentially mapped onto their inherent value.

When Tony and I were chatting about this, I was reminded of the idea of NP-completeness in terms of how we think about the problem of aesthetics. While it’s straightforward to know whether or not you like a specific poem or novel or painting—or digital artwork—it is much more difficult to create that specific work of art itself. Essentially, you can verify beauty, but it’s hard to generate it.

Now, as far as I know, there is no general-purpose algorithm for generating art. But if there were, it would be nice if the computational difficulty would map onto NP-completeness. In other words, as the “size” of the desired artwork grows, it would become much more computationally expensive, because art would remain rare and hard to find (though easy to verify as artistic). As a result of this, this would mean that the actual cost of an artwork could map onto its value. Would this finally provide a means of truly connecting artwork and NFTs?

Of course, a lot of this is no doubt ridiculous (and might be based on some fundamental crypto misunderstandings!), but I think there is value in thinking about how the blockchain, NP-completeness, and aesthetics contain some ideas that when mapped onto each other yield something thought-provoking.

Imagine a world where the energy expenditure of Bitcoin was instead being used to produce computationally-generated beauty…

Thanks to Tony Kulesa for discussions about this.

In Overedge Catalog news, I am interested in collecting unconventional revenue models for research organizations, such as research report subscriptions (such as Fast Forward Labs) or corporate membership/sponsorship (such as the Santa Fe Institute). If you know of interesting models, please pass them along.

I wrote a piece for The Atlantic about the recent Fastly internet outage: “Nobody Understands the Internet Until It Breaks

And some additional links worth checking out:

Also, alas, the signal from Proxima Centauri seems to just be interference.

Until next time.