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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...

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