In an 100-instruction function, do we necessarily care about all 100 instructions? Given our two sequential processes, what if we were to identify all external state accessed or modified by those processes (which should be fairly easy - for starters we can get a list of all non-stack memory addresses), forget about any state that is only used by one process, and considered the result? We'd have a list of 'interactions' between the processes.
Could we then process our 100-instruction program again, looking for instructions that refer to one of the interactions on our list, and breaking the instructions into section with one interaction per section? Think of each section as an 'instruction' from my previous post.
The way of arranging two 5-element programs is going to be smaller than two 100-element programs. The value is definitely less than 5^6 (15625).
