Definition
Knowledge representation is the branch of AI concerned with how to write down what a system knows so that a program can reason over it. The thing worth understanding first is that this is not a storage decision. The form you choose fixes what the system will be able to conclude and how long each conclusion takes: some inferences become cheap, some become exponential, and some become impossible for reasons that are theorems rather than engineering shortfalls.
Take one fact — every dog is a mammal. It can be a row in a table, an edge in a graph, a slot in a frame, an if-then rule, an axiom in first-order logic, or a direction in a vector space of a few hundred dimensions. All six hold the fact. They differ entirely in what you can then ask. The table cannot tell you that Rex is a mammal unless somebody also wrote that row. The graph answers by walking two edges. The logic answers by proof, and answers questions nobody anticipated — but a first-order prover asked a question whose answer is no may simply never return, and no faster machine fixes that.
That tension has a name. Hector Levesque and Ronald Brachman called it the expressiveness-tractability trade-off in a 1985 paper, developed in Expressiveness and tractability in knowledge representation and reasoning (Computational Intelligence 3, 1987): the more a language can say, the more expensive it is to reason with, and the expense grows dramatically rather than gradually. Knowledge representation is, in the end, the discipline of buying only as much expressiveness as you can afford to compute over.
This page is about that choice. If you want to design a domain schema in RDF or OWL, that is Ontologies. If you want the curated entity-and-relationship graph as a data asset, that is Knowledge Graphs (KG). The rule-and-logic paradigm as a whole is Symbolic AI, and the 1959 program that tried to reason with almost no knowledge at all is General Problem Solver (GPS).
How It Works
The choice is priced by a theorem, not by your hardware
Once you pick a representation language, the worst-case cost of reasoning in it is settled. It is not a property of your reasoner, your indexes or your cluster; it is a complexity class attached to the language itself. This is what makes knowledge representation a real engineering decision rather than a stylistic one, and the ladder below is the price list.
- Propositional logic — decidable, but satisfiability is NP-complete, the original result in Stephen Cook's The Complexity of Theorem-Proving Procedures (STOC, 1971).
- EL, the description logic behind the OWL 2 EL profile — subsumption is PTIME-complete, so classification is polynomial in the size of the ontology. Franz Baader, Sebastian Brandt and Carsten Lutz established the boundary in Pushing the EL Envelope (IJCAI 2005), and the W3C fixes it in the OWL 2 Profiles recommendation.
- ALC, the basic description logic with negation — concept satisfiability is PSPACE-complete (Schmidt-Schauß and Smolka, Attributive concept descriptions with complements, Artificial Intelligence 48, 1991).
- ALC once you add a general TBox — the same logic, plus the ability to state arbitrary class inclusions, jumps to EXPTIME-complete. Adding one construct moved the problem a whole complexity class.
- OWL 2 DL under direct semantics — N2EXPTIME-complete for consistency, satisfiability, subsumption and instance checking, per the same W3C recommendation.
- First-order logic — undecidable. Alonzo Church and Alan Turing independently settled the Entscheidungsproblem in 1936: no algorithm decides whether an arbitrary first-order sentence is valid. It is semi-decidable, which is the practically important refinement — a complete prover will eventually confirm a sentence that is valid, but given one that is not, it has no obligation to stop.
Read that list in one direction and it is a story about power. Read it in the other and it is a story about bills. The gap between the second entry and the fifth is the difference between classifying a 360,000-concept medical terminology overnight and not being able to promise an answer at all.
The 2ⁿ the bound is about
Complexity classes are abstractions, so it helps to see the concrete object they describe. A propositional formula over n variables has 2ⁿ possible truth assignments, and the naive way to check satisfiability is to try them. At n = 20 that is a million — nothing. At n = 60 it is about 1.15 × 10¹⁸, which at a billion assignments per second is roughly 36 years. At n = 300 it is about 2.0 × 10⁹⁰, more than the commonly cited estimate of 10⁸⁰ atoms in the observable universe. Three hundred yes/no facts is a very small knowledge base, and enumeration has already left physics behind.
That is why the complexity class matters. The difference between a polynomial language and an exponential one is not that one is slower; it is that one has a ceiling in the tens of thousands of assertions and the other does not.
The honest complication: worst case is not average case
The standard error, once someone has learned that SAT is NP-complete, is to conclude that propositional reasoning is hopeless. It is not, and pretending otherwise misreads what a worst-case bound claims. Sharad Malik and Lintao Zhang put the real position precisely in Boolean Satisfiability: From Theoretical Hardness to Practical Success (Communications of the ACM 52(8), 2009): an instance with a million variables is "considered within the reach of modern solvers", even though its search tree has 2^(10⁶) leaves and a day of computation visits perhaps a billion of them — about 2³⁰.
A billion nodes out of 2^(1,000,000) is not a fraction any ordinary word describes. The solver succeeds because real instances have structure — symmetry, locality, long chains of forced assignments — that clause learning and propagation exploit, so almost the whole tree is pruned without being visited. The lesson for representation design is not "ignore complexity", it is sharper than that: an NP-complete language with good solvers is often a better practical bet than an undecidable language with none, because in the first case you can be surprised in your favour and in the second you cannot.
What breaks when you get this wrong
The characteristic failure is not a crash. You choose an expressive language because it lets you say exactly what you mean, you write a few thousand axioms, and one day classification stops returning. There is no bug to find, no index to add, and no profiler output worth reading, because the cost was fixed the day the language was chosen. The only fix at that point is to re-express the knowledge in a weaker logic — which means revisiting every axiom that used the construct you now have to give up. Making that decision at the start costs an afternoon of reading complexity results. Making it after two years of knowledge engineering costs the knowledge base.
Types
The taxonomy below is the one the textbooks use, and it is genuinely a taxonomy: people writing knowledge-based systems in the 1970s and 1980s picked one of the first four and said which. The fifth arrived later and now dominates. What matters about each is not its shape but which inference it makes cheap.
Logic
Facts are sentences in a formal language and inference is proof. The payoff is that the sanctioned conclusions are exactly the ones that follow — soundness and completeness are provable properties, not aspirations, and the system can answer questions its author never considered. The price is the ladder above. Practical systems therefore almost never use full first-order logic; they use a deliberately crippled fragment. Description logics are the crippling done on purpose: each one is a named subset of first-order logic with a known complexity, chosen so that the reasoning you need is affordable.
Semantic networks
Concepts are nodes, relationships are labelled edges, and inference is traversal plus inheritance down is-a links. Ross Quillian introduced them in 1968 as a model of human semantic memory. What they make cheap is exactly what traversal is cheap at: relatedness, paths, inherited properties. What they lack is a semantics — early networks had no agreed answer to what an unlabelled link meant, which is why the family's descendants (knowledge graphs, RDF) come with an explicit formal reading attached.
Frames
Marvin Minsky's 1974 proposal: a concept is a record of named slots with default values, and inheritance fills the slots you did not state. A Bird frame with can-fly: yes by default answers a question about a bird you have never seen, and a Penguin frame overrides that slot. Frames made default reasoning natural — conclusions held unless contradicted — and default reasoning is exactly what strict logic refuses to do, since a classical theory has no notion of "true unless overridden". That expressive gain is why non-monotonic logics became a research field in their own right, and why they are hard.
Production rules
Knowledge as an unordered set of IF condition THEN action rules, fired by an inference engine against a working memory. This is the form that carried expert systems: the knowledge is modular, each rule is separately readable by a domain expert, and the chain of fired rules is a ready-made explanation of the answer. The cost is that a rule base has no global semantics — nothing tells you what a thousand rules jointly assert, whether they contradict, or what happens when two fire at once. That is a conflict-resolution policy, not a proof.
Distributed representations
Since the 2010s the field's centre has moved to learned vectors: a concept is a point in a continuous space, and inference is arithmetic on those points. See Embedding for how the vectors are produced and what the geometry means. The gain is real and large. Vector representations are acquired from data instead of authored by hand, degrade gracefully on inputs nobody anticipated, and represent similarity — the thing symbolic forms are worst at — natively.
The loss is equally precise, and it is the reason the older forms have not disappeared. A vector cannot be inspected, contradicted or corrected the way an assertion can. In a rule base you delete the rule; in an ontology you retract the axiom; in a knowledge graph you drop the triple. In a learned representation the fact is distributed across weights that also encode a million other facts, so there is no equivalent operation. Editing a single fact into a trained model is an open research problem with its own literature: Mass-Editing Memory in a Transformer (Meng et al., 2022) scales to "thousands of associations" in GPT-J (6B) and GPT-NeoX (20B), and that is reported as a result, because the baseline was one at a time.
Real-World Applications
SNOMED CT is a complexity result turned into a product decision
SNOMED CT is the clinical terminology used in health systems across dozens of countries; SNOMED International states that the monthly International Edition contains more than 360,000 concepts (as of publication). Every one of those concepts has to be classified — placed correctly in the subsumption hierarchy implied by its definition — and reclassified whenever definitions change.
That is only possible because the terminology is expressed in a deliberately weak logic. The W3C notes that OWL 2 EL "provides class constructors that are sufficient to express the very large biomedical ontology SNOMED CT", and EL was extended in Pushing the EL Envelope with precisely the constructs SNOMED needs and nothing that would break polynomiality. Had the same content been written in a logic one rung up, classification would have been at best PSPACE and in practice would not finish. The expressiveness that was given up — most conspicuously negation and disjunction — is the price paid, in the open, for a terminology that can be recompiled every month.
Cyc: the largest sustained bet on hand-coded knowledge
Douglas Lenat began Cyc in 1984 on the premise that commonsense reasoning needed millions of explicitly written assertions and that no shortcut existed. In Getting from Generative AI to Trustworthy AI: What LLMs might learn from Cyc (2023) Lenat and Gary Marcus report the cost from the inside: "four decades, 2000 person-years" to produce a knowledge base comprising "tens of millions of hand-authored assertions".
Two arithmetic consequences are worth extracting. Two thousand person-years spread over four decades is about 50 people sustained continuously for forty years. And if the base is taken at the commonly cited figure of roughly 24.5 million assertions, that is about 12,000 assertions per person-year, or — at 2,000 working hours in a year — one formal assertion every ten minutes of every working hour, for forty years. Cyc's published assertion counts vary considerably between tellings, so treat the total as an order of magnitude rather than a measurement; the rate is the durable point, and it is why hand-authored knowledge does not scale to the open world by effort alone.
Propositional logic in verification
The weakest language on the ladder is the one with the largest industrial deployment. Hardware and software verification tools encode a property to be checked as a Boolean formula and hand it to a SAT solver: bounded model checking asks whether a bad state is reachable in k steps by unrolling the transition relation k times, and the answer is a satisfying assignment or a proof there is none. The representation is chosen for its solvers, not for its expressive power — nobody would call propositional logic a good language for describing a processor — and it works because the pruning above turns a nominally hopeless class into a routine tool.
Key Concepts
A representation is five things at once
The most useful answer to "what is a knowledge representation" comes from Randall Davis, Howard Shrobe and Peter Szolovits, What Is a Knowledge Representation? (AI Magazine 14(1), 1993). They argue it plays five roles simultaneously, and that these roles make conflicting demands: it is a surrogate for the thing itself; a set of ontological commitments, an answer to "in what terms should I think about the world?"; a fragmentary theory of intelligent reasoning, since it sanctions some inferences and recommends others; a medium for efficient computation; and a medium of human expression.
The third role is the one that makes this term worth a page. As they put it, "representation and reasoning are inextricably, and usefully, intertwined: a knowledge representation is a theory of intelligent reasoning." Their image for the second role is the sharpest sentence in the literature: a representation is "a strong pair of glasses that determine what we can see, bringing some part of the world into sharp focus, at the expense of blurring other parts." Choosing a representation is choosing what your system will be structurally unable to notice.
Expressive is not a synonym for good
The habit that costs projects the most is treating expressiveness as a quality score. Every rung of the ladder is a counterexample: the language you want is the weakest one your actual queries can be stated in, because that is the one whose reasoning terminates in a time you can budget for. Reaching for full first-order logic when a polynomial fragment would do is not ambition; it is a decision to give up on finishing the computation.
Challenges
Writing down what does not change costs more than reasoning about what does
The frame problem, stated by McCarthy and Hayes in 1969, is that to describe an action you must also describe everything the action leaves alone. Its naive cost — one axiom per action-fluent pair — is set out on General Problem Solver (GPS); what belongs here is that the cost is a property of the encoding, not of the world, and a better encoding removes it.
Work it on a domain: a household robot with 50 actions and 200 fluents. Naively you need a frame axiom for each action-fluent pair in each polarity — 2 × 50 × 200 = 20,000 axioms, none of which says anything, all of which must be maintained. Ray Reiter's 1991 successor-state axioms reorganise the same content by fluent rather than by action: one axiom per fluent saying exactly when it holds in the next situation, plus one precondition axiom per action. That is 200 + 50 = 250 axioms, an 80× reduction, with no loss of content. The frame problem was never a fact about robots. It was a fact about a representation, and it dissolved when the representation changed — which is the whole thesis of this page in one worked example.
Acquisition is the bottleneck, and it is a rate problem
Edward Feigenbaum named the knowledge-acquisition bottleneck in the 1970s, and Cyc's rate above puts a number on it: an assertion every ten minutes, sustained for four decades, still does not exhaust common sense. Extraction from text moves the bottleneck rather than removing it, because extracted assertions arrive with error rates that a logic — which propagates a false premise into every conclusion that depends on it — is unusually badly equipped to absorb. A single contradictory pair in a classical knowledge base makes everything derivable.
The correction problem in learned representations
The move to distributed representations solved acquisition and created its opposite. When knowledge lives in weights, there is no assertion to retract, so the ordinary maintenance operations of a knowledge base — delete this fact, mark that source untrusted, show me why you concluded this — have no counterpart. That absence is the practical reason explicit stores survive alongside Large Language Models (LLM): Retrieval-Augmented Generation (RAG) exists largely so that the knowledge a system answers from is in a place a human can edit and cite, and work on Explainable AI (XAI) is an attempt to recover the inspectability that the older forms had for free.
The design question that follows is not "symbolic or neural". It is which facts need to be correctable one at a time, and how much of the ladder you can afford for those.