> as a programmer I can guarantee this solution is completely useless Oh absolutely, you'd never want to run such a program. However, it's existence is a usefu

> as a programmer I can guarantee this solution is completely useless Oh absolutely, you'd never want to run such a program. However, it's existence is a useful mathematical trick. Similar to a brute-force chess program: it's not practical to run, but it's existence tells us a lot about chess (e.g. that it doesn't require conciousness, or other such woo). > you do need to find the program first Note that there are two programs being considered: a program P which directly solves NP problems in P-time; and a "universal search" program which indirectly solves NP problems in P-time. The universal search definitely solves the problem (assuming P exists), since it brute-forces the outputs of all programs, until it finds a valid solution. Eventually it will either reach the output of P (which is a valid solution); or it will stop earlier by finding some other solution first. Let's assume the worst case, that it doesn't find anything before P's solution: how long will this search take? Let's ignore Python and stick to some simple binary encoding (e.g. for some Turing machine, or whatever). We'll make our encoding prefix-free by using '11' to indicate the 'end of program'; hence every binary string which only contains '11' at the end is a valid program. Here are the first few, arranged by length: Length 0 = [] Length 1 = [] Length 2 = [11] Length 3 = [011] Length 4 = [0011, 1011] Length 5 = [00011, 01011, 10011] Length 6 = [000011, 001011, 010011, 100011, 101011] ... We're using a binary alphabet, so we'll divide up our runtime between these programs using powers of 2, such that each gets a fraction 1/(2^length): the program of length 2 gets 1/2^2 = 1/4 of our runtime; the program of length 3 gets 1/2^3 = 1/8 of our runtime; the programs of length 4 each get 1/2^4 = 1/16 of our runtime; and so on. This exponential allocation ensures that we never allocate more than 100% of our runtime (similar to the sum 1/2 + 1/4 + 1/8 + ... never exceeding 1). The prefix-free encoding ensures that longer programs only exist in the "gaps" left by shorter programs (e.g. imagine every program arranged as leaves of a binary tree; tracing the left/right paths down through the tree gives us a prefix-free encoding). Fun fact: the parent used UTF-8 because that's a prefix-free encoding. The program P will have some binary encoding in this scheme; let's say its length is L bits. L is just a constant: it has nothing to do with the particular NP problem instance we want to solve; e.g. if we're solving a traveling salesman problem, the length of the program P has nothing to do with the number of cities we want to visit. According to the above scheme, universal search will spend 1/2^L of its time running P: that is exponential in L but independent of our problem size (e.g. the number of cities our salesman is visiting). Hence universal search will run one step of P for each 2^L of its own steps; that's probably quite a large, impractical slow-down, but as far as complexity theory's concerned it's only a constant factor. If running P directly has some polynomial time complexity like O(N^A) for some power A, then universal search will have complexity O(2^L × N^A) = O(N^A) since the constant factor is dominated by the polynomial factor. You may be left wondering how universal search can keep track of all these running programs. There are actually several ways to do it, depending on preference. One particularly simple approach is the "FAST" algorithm: this only runs one program at a time, and just restarts everything from scratch over and over. For example, we can run 11 for one step, and see if it's made a valid solution; if not, start again by running 11 for two steps, then 011 for one step; if neither found a solution, start again by running 11 for four steps, then 011 for two steps, then 0011 for one step, then 1011 for one step; and so on. This exponential-restarting ends up taking twice as long, but that's just another constant factor we can ignore https://people.idsia.ch/~juergen/toesv2/node28.html https://people.idsia.ch/~juergen/toesv2/node28.html Yet another approach is to choose programs and divide up our runtime using probabilities (e.g. coin tosses). The GUESS algorithm performs the same program-length-based allocation as FAST, but is embarrassingly parallel rather than sequential https://people.idsia.ch/~juergen/toesv2/node31.html https://people.idsia.ch/~juergen/toesv2/node31.html If you don't like linear factors, you can also use Hutter Search: that starts off by running universal search, but in parallel it performs a brute-force search for proofs that some other program both is equivalent and faster (such as P, in the above example). It uses exponential restarts (like FAST), which lets it switch to a faster program once found. Hutter Search only has a small linear slowdown (depending on how often we restart, and how we divide our resources between running our current solution and searching for provably-faster ones). Instead, it has a colossal (but constant!) additive factor (the time spent finding a provably faster program, then waiting for the next restart so it can switch to running that)