Complexity of Inference
Fabrizio Riguzzi · River Publishers eBooks · 2023
Inference includes a variety of tasks. In this chapter, the authors provide a list of inference tasks and then, after introducing some background on complexity theory, they present the result on the complexity of the various tasks that are present in the literature. The complexity class PP consists of the languages that are decided by a probabilistic Turing machine in a number of steps polynomial in the input size, with an error probability strictly less than 1/2 for all input strings. A program is locally stratified if there exists a level mapping for ground atoms such that the level of each atom in the head of each ground rule is strictly greater than the level of each negative literal in the body and greater or equal than the level of each positive literal. The requirement of rationality of the numbers is imposed in order to be able to represent them as a pair of binary integers in the input.