On the complexity of Strictly Coherent Books

IMG_20170828_111440_480.jpg Given an book on formulas (i.e., a partial map on SL to rational numbers of [0,1]), deciding if it is coherent is an NP-complete problem. The proof essentially uses Carathéodory theorem which characterizes the points of a convex set: given a convex set C=cl-co(X) whose affine dimension is n, then x belongs to C if and only if there is a finite subset Y of X of cardinality at most n+1, such that x is a convex combination of the elements of Y. Indeed a book is coherent if and only if it belongs to cl-co(H) being H the set of logical valuations.

Moving from coherence to strict-coherence essentially boils down, in geometrical terms, to providing a characterization, á la Carathéodory, for the relative interior of cl-co(H). Steinitz theorem gives a (unfortunately useless) direction: if a point x belongs to relint cl-co(H), then there exists a finite subset K of H of cardinality at most 2n such that x belongs to relint cl-co(K). The converse direction (which is key for the decidability of a strictly coherent book) is trivially false: consider a cube C in R3 and pick a point x lying in the relint of a face of C. Then x belongs to the relative interior of a square, but not to the relint of the cube.

In the last weeks I’m just trying to extend (in certain sense) Steinitz theorem to obtain a characterization of the relative interior of a convex set. I don’t know if I will get it, but I like very much the drawings.

Author: tomflaminio

Ramón y Cajal Researcher at the Artificial Intelligence Research Institute of Barcelona

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s