Boolean Nearest Neighbor Language in the Knowledge Compilation Map

The Boolean Nearest Neighbor (BNN) representation of

Boolean functions was recently introduced by Hajnal, Liu

and Turan. A BNN representation of function f is a pair

(P,N) of sets of Boolean vectors (called positive and

negative prototypes) where f(x) = 1 for every positive

prototype x ∈ P, f(x) = 0 for every negative prototype x ∈

N, and the value f(x) for x not in (P ∪ N) is determined

by the type of the closest prototype. The main aim of this

paper is to determine the position of the BNN language in

the Knowledge Compilation Map (KCM). To this end, we settle

the complexity status of most standard queries and

transformations (those listed in KCM) for BNN inputs. We

also compare the succinctness of the BNN language with

several languages considered in KCM.