Is there an “Implex Method” in complexity theory?
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 step
father. 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:
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?
Like this:
Like Loading...
Related
;
;
(etc.);
.
Acyclic digraph is preferable, because dag = a lump of matted wool and feces hanging from the rear end of a sheep. (Excuse my Australian.)
In an article positing incestuous offspring, I think that’s the least of our worries!
Ha-ha, Jon and George. I actually did notice the word “Dag” in the “dwyl” dictionary and found what it is. I discreetly decided to avoid mentioning it 🙂 .
I also thought about inserting a reference to Wordsworth’s line “The child is the father of the man” in the last paragraph about inverting the ancestor relation for Boolean functions, then mentioning Bill Wyman again. But the song of that title is Beach Boys, not Stones. 😉
It’s been a while but I think I used to call these radigraphs, for Rooted Acyclic Digraphs (with all the arcs pointing away from the root). The schools of graph theory, mostly MiGhTy, I passed through were very fussy about terminology, as opposed to those hippy-dippy California cults. They would say digraph is actually preferable to directed graph on both English grammar and category theory counts. The reason being an adjective added to a substantive term indicates either a species of a genus or else an operation performed on each member of a class. But directed graphs are not begot by selection or transformation of graphs, they are a synthetic category all their own. All that makes directed acyclic graph multiply bad nomenclature.
My new paper in a peer-reviewed journal:
http://www.iapress.org/index.php/soic/article/view/1327/881