Challenges Overview
A challenge within the context of TIG is a computational problem adapted as one of the proof-of-works in OPoW. Presently, TIG features four challenges: boolean satisfiability, vehicle routing, vector range search and the knapsack problem. Over the coming year, an additional seven challenges from domains including artificial intelligence, biology, medicine, and climate science will be phased in.
The Innovation Game focuses on a category of problems that we call “asymmetric” problems. These are problems that require significant computational effort to solve, but once a solution is proposed, verifying its correctness is relatively straightforward.
Some areas where asymmetric Challenges potentially suitable for The Innovation Game include:
-
Mathematical Problems: There are a great many examples of asymmetric problems in mathematics, from generating a mathematical proof to computing solutions to an equation. Zero knowledge proof (ZKP) generation, Prime factorisation, and the discrete logarithm problem are further examples of asymmetric problems which have significant implications in cryptography and number theory. NP-complete problems are simple to check and generally considered unsolvable within polynomial time. Such problems are fundamental in science and engineering. Examples include the Hamiltonian Cycle Problem and the Boolean Satisfiability Problem (SAT).
-
Optimisation Problems: Optimisation problems are at the core of numerous scientific, engineering, and economic applications. They involve finding the best solution from all feasible solutions, often under a set of constraints. Notable examples include the Travelling Salesman Problem and the Graph Colouring Problem. Optimisation problems are also central to the training of machine learning models, and the design of machine learning architectures such as the Transformer neural network architecture. These include gradient descent, backpropagation, convex optimisation.
-
Simulations: Simulations are powerful tools for modelling and understanding complex systems, from weather patterns to financial markets. While simulations themselves may not always be asymmetric problems, simulations may involve solving problems that are asymmetric, and these problems may be suitable for The Innovation Game. For example, simulations often require the repeated numerical solving of equations, where this numerical solving is an asymmetric problem.
-
Inverse Problems: Inverse problems involve deducing system parameters from observed data and are generically asymmetric. These problems are ubiquitous in fields like geophysics, medical imaging, and astronomy. For example, in medical imaging, reconstructing an image from a series of projections is an inverse problem, as seen in computed tomography (CT) scans.
-
General Computations: Any calculation can be made efficiently verifiable using a technique called “verifiable computation”. In verifiable computation, the agent performing the computation also generates a proof (such as a zero knowledge proof) that the computation was performed correctly. A verifier can then check the proof to ensure the correctness of the computation without needing to repeat the computation itself.
