ISSN:
1436-4646
Keywords:
Convex polytopes
;
symmetries
;
NP
;
co-NP
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A family of polytopes, correlation polytopes, which arise naturally in the theory of probability and propositional 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01594946
Permalink