Is there an “Implex Method” in complexity theory?

Wikipedia src

Bill Wyman was the bass guitarist of the Rolling Stones until 1993. He married Mandy Smith in 1989. A few years later, in 1993, his son, Stephen Wyman, married Mandy Smith’s mother, Patsy Smith. Had Bill and Mandy not divorced by then, Wyman would have been his own stepfather. Which Wyman do we mean? Both of them.

Today we investigate the level of degeneracy in “family tree” type graphs.

We say “family tree” but it cannot be a tree. If your great-grandparents were all distinct for every value of , then at you would have over one billion distinct ancestors at that level—and two billion in your whole tree—virtually all born after the year 1100 CE. The world population is estimated not to have passed one billion until after 1800.

At least we can say it cannot have cycles. You cannot be your own biological grandfather, for reasons more fundamental than not being able to go back in time to kill your grandfather. Thus the graph is a DAG—a directed acyclic graph. Is “DAG” a jargon term? It should be regarded as common—it is, after all, the stuff of us.

Implex and Amplex

The fact that you are descended by multiple paths from common ancestors is called pedigree collapse by Wikipedia, rather dramatically.

The degree of pedigree collapse, meaning the difference between and your actual number of level- ancestors—is called the implex. This is not a legal word in official US Scrabble (TM), but does appear on the larger US-UK SOWPODS list.

The ratio strikes me as more natural than the difference. To keep it representing “collapse,” one would have to do , but the original ratio is more convenient in what follows. I propose calling it the amplex, saying how ample one’s DAG of ancestors is. This term is not in SOWPODS but does appear (along with implex) in a downloadable dictionary of 466,551 meaningful words and names and abbreviations compiled by the organization dwyl for “Do What You Love.” The word amplex originally means to engage in a process by which some amphibians make ample trees—or rather DAGs—of descendants.

The ratio may be expected to stabilize once becomes moderately large. We can say similar about the differences as grows. Finally, the ratio is a technically different but similarly motivated notion of amplex. These logarithmic forms are most akin to information complexity measures.

An Example

For an example of implex and amplex, let Alice have a completely unique tree of ancestors, so zero collapse and amplex ration . Then Alice’s full brother, named Bob of course, has the same. Suppose Alice and Bob incestuously marry and have a child C. Then for to , C has implex in the difference form, or in the ratio form. The amplex ratio is also .

Now suppose instead that Alice and Bob come from different families and each have amplex , i.e., (where refers to Bob’s set of level- ancestors) at level . Then their child D at level has amplex at most . The maximum is achieved when Alice and Bob are unrelated to each other—i.e., the sets and of their respective ancestors (saying out to level ) are distinct. If they coincide, then D will have amplex only .

It may seem intuitively wrong that the incestuous child C could have higher amplex—lower implex—than the child of unrelated parents, each with a reasonable ratio. This hints that some further modifications of these measures may be more effective, such as weighting differences of closer ancestors more. Insofar as different paths to the same level- ancestor define an equivalence relation on binary strings of length , there are notions of prefixes and prefix-freedom that are relevant.

I won’t try to sort such notions out now. I am only trying to be suggestive and invite reader suggestions. In the real world, genomics brings much more extensive notions of genetic diversity. What might help the world of computational complexity theory is more in mind here.

Analogy With Boolean Functions

There are various ways to set up a parenthood notion for Boolean functions. Given two Boolean functions and , any of the following can be regarded as an offspring:

• (etc.);

The idea that we are trying to tap into is the following: In complexity theory, we want to prove that a set of functions are hard, meaning they do not have Boolean circuits of a given small size . The sets of hard functions overall are large, but we mean sets of functions that are known in some other way, such as belonging to families that define problems in . For the most part, it suffices to prove that some member of such an is hard.

The usual mindset is to prove that circuits of size have insufficient “virility” to compute members of The idea I wish to suggest instead is to try to prove that they are too incestuous—that too many of them compute copies of the same function. Then show that they cannot encompass all of

To make this work in the above framework, we may need to invert the notion of Boolean “offspring” suggested above, so that the ultimate function computed is styled as an ancestor. In any event, the idea is to structure the counting so that size- circuits cannot have all the members of in their collective “gene pool”—so that some member of must go uncomputed.

Open Problems

Can you suggest further notions in genealogy—without going into genetics—and can they help resolve impasses in complexity?