Thursday, August 26, 2004
Deductive Algorithmic Knowledge
Deductive Algorithmic Knowledge is a paper by Riccardo Pucella of Cornell University.
"Abstract
The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a logical theory, rather than a particular algorithm, can be used to capture the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge, where the latter is given with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of such logical theories leads to very natural axiomatizations of the resulting logic when interpreted over a fixed deductive system. The decision problem for the logic is NP-complete in general, no harder than propositional logic, and moreover, it remains NP-complete when we fix a tractable deductive system. The logic extends in a straightforward way to multiple agents, where the decision problem becomes PSPACEcomplete."
"Abstract
The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a logical theory, rather than a particular algorithm, can be used to capture the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge, where the latter is given with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of such logical theories leads to very natural axiomatizations of the resulting logic when interpreted over a fixed deductive system. The decision problem for the logic is NP-complete in general, no harder than propositional logic, and moreover, it remains NP-complete when we fix a tractable deductive system. The logic extends in a straightforward way to multiple agents, where the decision problem becomes PSPACEcomplete."
0 Comments:
