Correlation polytopes: Their geometry and complexity

A family of polytypes, correlation polytopes, which arise naturally in the theory of probability and propostional logic, is defined. These polytopes are tightly connected to combinatorial problems in the foundations of quantum mechanics, and to the Ising spin model. Correlation polytopes exhibit a great deal of symmetry. Exponential size symmetry groups, which leave the polytope invariant and act transitively on its vertices, are defined. Using the symmetries, a large family of facets is determined. A conjecture concerning the full facet structure of correlation polytopes is formulated (the conjecture, however, implies that NP=co-NP). Various complexity results are proved. It is shown that deciding membership in a correlation polytope is an NP-complete problem, and deciding facets is probably not even in NP. The relations between the polytope symmetries and its complexity are indicated.