33
votes

### What problem would you base your mathcoin on?

I'd choose $R(5,5)$ and other unknown Ramsey numbers, since
"Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of $R(5, 5)$ or they ...

Community wiki

22
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Have you considered unknotting knots?
The problem would be finding a sequence of Reidemeister moves for a random link graph that reduces it to the unknot. In some cases, no such sequence would exist, ...

- 3,271

15
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Calculating the permanent of a small matrix is a computationally challenging problem, as discussed here, here, and here. See also the Wikipedia article.
Given an $n \times n$ matrix $A$, a naïve ...

- 1,615

14
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Finding cycles in graphs is a standard graph theory problem that lends itself well to proof-of-work. See my Cuckoo Cycle project page at
https://github.com/tromp/cuckoo which has tons of details, as ...

- 1,519

13
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

I find this to be an excellent suggestion, though not sure all requirements can be satisfied. More specifically, 3 and 5 - if we randomly generate instances, then why would they have any intrinsic ...

- 17.6k

12
votes

Accepted

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Here is a recent paper, which has been received positively in the cryptocurrency community. I will expand on this paper here.
While conventional hash functions do not allow one to construct very ...

- 24.6k

11
votes

### What problem would you base your mathcoin on?

In Conways game of life, there is a the concept of an orphan pattern.
Basically, an orphan is a finite pattern such that each configuration containing that pattern is a Garden of Eden (a pattern that ...

Community wiki

10
votes

### What problem would you base your mathcoin on?

Homotopy groups of spheres. We know far too little about them!
It can be made computationally feasible by choosing finite simplicial complexes and allowing subdivision. Maps of simplicial complexes ...

Community wiki

10
votes

### What problem would you base your mathcoin on?

Maybe finding good error-correcting codes. For instance, given $q, n, M$, search for a set of $M$ strings, each of length $n$ from a $q$-sized alphabet, with largest $d$, where $d =$ minimum pairwise ...

Community wiki

9
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Discussion of the prospect of a cryptocurrency based on cellular automata prompted me to start developing the Catagolue project in the summer of 2014. The proof-of-work system was deliberately chosen ...

- 11.8k

9
votes

### What problem would you base your mathcoin on?

Apologies if this answer is nitpicky and diverges slightly from the questions intent, but this particular soft question appears to warrant a soft answer.
Implicit in your term "mathcoin" are ...

Community wiki

7
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Let me have another go, because I really love this question. Essentially it's like a SETI@home project - without going into details, let's just consider the theoretical model that some signals arrive ...

- 17.6k

7
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

I don't see how you will have a problem which is progress free but still in NP(requirement 7); or any kind of problem that is suitable for your purpose for that matter. To see why this seems unlikely ...

- 179

6
votes

### What problem would you base your mathcoin on?

I would like to like to run Siemion Fajtlowicz's program Graffiti, or variants of it, to discover new conjectures, and accumulate more empirical evidence for its existing conjectures.

Community wiki

6
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Has anyone considered improving a best lower bound on $\Omega_U$ by finding small programs $p_i$ that halt, where $\Omega_U$ is a Chaitin halting probability of a universal prefix-free Turing machine $...

- 1,615

5
votes

### Which hard mathematical problems do you have to solve to earn bitcoins ?

Another way to earn bitcoin is not to mine them, but to have them wired to you from other bitcoin accounts. The transactions are signed using ECDSA. So if you solve the discrete logarithm problem in ...

- 1,166

4
votes

### What problem would you base your mathcoin on?

A semi-magic square is a square matrix with integer entries and all row and column sums equal. Every semi-magic square can be expressed as a linear combination, with integer coefficients, of ...

Community wiki

3
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

In 1996 Pascal Koiran showed that, assuming the Generalized Riemmann Hypothesis, Hilbert's Nullstellensatz is in $\mathsf{AM}$ over the complex numbers $\mathbb{C}$. That is, given a system $S$ of ...

- 31

3
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Just to point out this is already implemented in primecoin.
Primecoin network searches for special prime number chains known as Cunningham chains and bi-twin chains. The distribution of these prime ...

- 23.7k

2
votes

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

It is shown in http://eprint.iacr.org/2017/203.pdf that you can convert many nice problems to challenges, and in https://cstheory.stackexchange.com/a/39902/419 that any problem can be converted into a ...

- 17.6k

1
vote

### What computational problems would be good proof-of-work problems for cryptocurrency mining?

Community Wiki just to spitball some ideas
Around July 2018, the hash rate of Bitcoin - the number of hashes per second - has been hovering around $45$ million Terahashes/$s$. Further, the order of ...

Community wiki

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

bitcoins × 6cryptography × 4

soft-question × 1

sequences-and-series × 1

computational-complexity × 1

knot-theory × 1

gm.general-mathematics × 1

teaching × 1

experimental-mathematics × 1

quantum-computation × 1