Deductive Algorithmic Knowledge

It is well known that the standard model of knowledge based on possible worlds is subject to the problem of logical omniscience, that is, the agents know all the logical consequences of the ir knowledge [Fagin, Halpern, Moses, and V ardi 1995, Chapter 9]. Thu s, possible-world definitions of knowledge make it difficult to reason about the knowledge tha t agents need to explicitly compute in order to make decisions and perform actions, or to capture si tuations where agents want to reason about the knowledge that other agents need to explicitly com pute in order to perform actions. This observation leads to a distinction between two forms of knowledge, implicit knowledge and explicit knowledge (or resource-bounded knowledge), a distinction long recog nized [Rosenschein 1985]. The classical AI approach known as the interpreted symbolic structures approach, where knowledge is based on information stored in data structures of the agent, can be seen as an instance of explicit knowledge. In contrast, the situated automata approach, which interprets knowledge based on information carried by the state of the machine, can be seen as an instance of implicit knowledge. Levesque [1984] makes a similar distinction bet ween implicit belief and explicit belief. While the possible-worlds approach is taken as the standard model for implicit knowledge, there is no standard model for explicit knowledge.