Kunne man lagd en blockchain som, heller enn å outputte hash-values med et visst antall nuller, mines ved å løse 3SAT-problemer? Kunne da blitt lagret i en gigantisk tabell, og man kunne brukt de eksisterende reduksjonene til å konvertere et hvilket som helst NP-problem til 3SAT, og sett om svaret var i tabellen. Business opportunity: la bedrifter sjekke om 3SAT-problemet har blitt løst enda, og la den som løste 3SAT-en selge løsningen til de dersom ja. Utfordring: 3SAT er vanskelig i worst case, ikke nødvendigvis average case. Går det an å generere 3SAT-oppgaver med garantert hardness? Kanskje ikke. Finnes det noe [[NP]]-komplett problem med worst-to-average case hardness reduction? Eller er dette noe som ikke *kan* finnes? A: Indeed—[men det er ikke et trivielt resultat!](https://en.wikipedia.org/wiki/Average-case_complexity) > In 1993, Feigenbaum and Fortnow showed that it is not possible to prove, under non-adaptive random reductions, that the existence of a good-on-average algorithm for a **distNP**-complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems in **NP**. In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions. These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions. Løsning: bruk et [[distNP]]-komplett problem istedet, f.eks. [The Bounded Halting Problem](https://en.wikipedia.org/wiki/Average-case_complexity) (dog usikker på i hvor stor grad nytteverdien av løsningene går ned da i forhold til 3SAT—er det mange interessante og nyttige problemer i distNP?). Urelatert spørsmål: Hva er kvanteanalogien til distNP? --- En alternativ (og kanskje mer opplagt men mindre gjennomførbar) idé er å finne en måte bruke de til å trene maskinlæringsmodeller, hvor "the proof" er et kryptografisk bevis for beregningen (tror de eksisterer?). Mister det veldig tydelig "suksess"-kriteriet som bitcoin bruker for å avgjøre når en coin mines da. **Skrinlagt:** Som Martijn minnet meg på, problemet med eksponensielle områder er at selv om hele menneskeheten gjorde alt de kunne i milliarder av år ville man aldri gjort "a dent". Til illustrasjon: Det er så mange kombinasjoner av 52 kort at for hver gang man stokker en kortstokk (antatt at det er en god stokking) så er sannsynligheten for at rekkefølgen du ender opp med har oppstått før så godt som eksakt $0\%$.