Knowledge graph complexity
The same exponent that prices a circuit prices a knowledge graph.
Reasoning cost is a width cost
Answering a conjunctive query over a knowledge graph, or running inference across its relations, has cost governed by the treewidth of the query and the graph. Acyclic queries — treewidth 1 — are answerable in linear time (Yannakakis's algorithm); cyclic, high-width queries are not.
This is the database theorist's version of the same meter physicists and graph theorists use. A schema engineered for low treewidth keeps queries fast; one that accumulates dense cross-links pays the exponential.
Designing for the meter
If you control a knowledge graph's schema, you are implicitly choosing its treewidth, and therefore its reasoning cost. The shadow–mirror frame says: separate what can be separated, and reserve the irreducible coupling — the high-width core — for the connections that genuinely cannot be factored apart.
Questions
Why are acyclic queries fast?
Acyclic conjunctive queries have treewidth 1 and are solvable in linear time by Yannakakis's algorithm. Cycles raise the width and the cost.
Does treewidth apply to graph databases?
Yes — query evaluation cost is parameterized by treewidth just as graph algorithms are. Low-width schemas are the tractable ones.