(This was inspired by Gabriel’s post on Super Hard problems)
Trapdoor Functions and Prime Insights
One intuition is that solving hard problems is like finding the secret key to a trapdoor function. Funnily enough, the existence of trapdoor functions relies on conjectures implying P≠NP so the existence of barriers in the PvsNP conjecture is possibly no coincidence. I suspect that we will need to understand computational complexity perhaps intelligence & learning theory significantly better to be able to give convincingly quantify why some problems are Super Hard.
Strictly speaking, we can’t prove trapdoor functions exists but we do use functions which we suspect to be trapdoor functions all the time in cryptography.
Example. One simply example of a suspected trapdoor function is factoring a composite number.
Given a product of two large primes N=pq the problem is to find the prime factorisation. If I give you p, it is easy to find q by polynomial time division. In this sense the prime p (or symmetrically q) is akin to an ‘insight’.
More generally, we may consider a factorization N=p1⋯pk of a product of k primes. Each prime serves as a ‘separate’ discoverable insight.
One would like to argue that because of the Unique Factorisation Theorem the only way to find the factorisation of N is to find each of these prime factors step-by-step. In other words, the each prime represents a ‘necessary insight’. This argument is not quite sound for subtle arithmetic reasons but it might give a flavor of what we mean when we talk about ‘necessary insights’.
(This was inspired by Gabriel’s post on Super Hard problems)
Trapdoor Functions and Prime Insights
One intuition is that solving hard problems is like finding the secret key to a trapdoor function. Funnily enough, the existence of trapdoor functions relies on conjectures implying P≠NP so the existence of barriers in the PvsNP conjecture is possibly no coincidence. I suspect that we will need to understand computational complexity perhaps intelligence & learning theory significantly better to be able to give convincingly quantify why some problems are Super Hard.
Strictly speaking, we can’t prove trapdoor functions exists but we do use functions which we suspect to be trapdoor functions all the time in cryptography.
Example. One simply example of a suspected trapdoor function is factoring a composite number.
Given a product of two large primes N=pq the problem is to find the prime factorisation. If I give you p, it is easy to find q by polynomial time division. In this sense the prime p (or symmetrically q) is akin to an ‘insight’.
More generally, we may consider a factorization N=p1⋯pk of a product of k primes. Each prime serves as a ‘separate’ discoverable insight.
One would like to argue that because of the Unique Factorisation Theorem the only way to find the factorisation of N is to find each of these prime factors step-by-step. In other words, the each prime represents a ‘necessary insight’. This argument is not quite sound for subtle arithmetic reasons but it might give a flavor of what we mean when we talk about ‘necessary insights’.