Correlation polytopes: Their geometry and complexity (Q1176573): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Set OpenAlex properties.
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proposed Experiment to Test Local Hidden-Variable Theories / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quantum probability - quantum logic / rank
 
Normal rank
Property / cites work
 
Property / cites work: Neural networks and physical systems with emergent collective computational abilities. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4433663 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Best Possible Inequalities for the Probability of a Logical Function of Events / rank
 
Normal rank
Property / cites work
 
Property / cites work: Boole's logic and probability. A critical exposition from the standpoint of contemporary algebra, logic and probability theory. 2nd ed., rev. and enlarged / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5761948 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Probability of the Occurrence of at Least $m$ Events Among $n$ Arbitrary Events / rank
 
Normal rank
Property / cites work
 
Property / cites work: Best Linear Bonferroni Bounds / rank
 
Normal rank
Property / cites work
 
Property / cites work: An upper bound for the probability of a union / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the probability of a Boolean polynomial of events / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bivalent trees and forests or upper bounds for the probability of a union revisited / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3050157 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4739657 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of satisfiability problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of facets (and some facets of complexity) / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf01594946 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2064263748 / rank
 
Normal rank

Latest revision as of 11:17, 30 July 2024

scientific article
Language Label Description Also known as
English
Correlation polytopes: Their geometry and complexity
scientific article

    Statements

    Correlation polytopes: Their geometry and complexity (English)
    0 references
    0 references
    25 June 1992
    0 references
    The author is dealing with the facial structure of the correlation polytope \(P\), which can be defined as follows: for an integer \(n\) let \(S\subseteq K_ n=\{(i,j)\mid 1\leq i<j\leq n\}\) and \[ {\mathcal R}(n,S):=\{u(\varepsilon)=(u_ 1(\varepsilon),\dots,u_ n(\varepsilon),u_{12}(\varepsilon),\dots, u_{ij}(\varepsilon), \dots,u_{n-ln}(\varepsilon)\mid \] \[ u_ i(\varepsilon)=\varepsilon\hbox{ for }i=1, \dots,n; u_{ij}(\varepsilon)= \varepsilon_ i\cdot\varepsilon_ j\hbox{ for all }(i,j)\in S, \varepsilon=(\varepsilon_ 1,\dots,\varepsilon_ n)\in\{0,1\}^ n\} \] a set of vectors corresponding to \(S\); then \(P(n,S)\) is the convex hull of \({\mathcal R}(n,S)\) and especially \(P\) the convex hull of \({\mathcal R}(n,K_ n)\). It is shown that \(P(n,S)\) has a non-empty interior and that its facial structure has a large symmetric group; thus one gets an exponential number of different facets by application of the symmetries. Some facets are determined. Furthermore the author proves that the corresponding decision problem (given a vector \(p\in\mathbb{R}_ +^{n(n+1)/2}\); is \(p\in P\)?) is \(NP\)-complete. This means that unless \(NP=co-NP\) deriving all the inequalities for \(P\) is an ``impossible'' task. The name ``correlation polytope'' stems from the fact that every point of \(P(n,S)\) can be interpreted in terms of certain probability assignments.
    0 references
    facial structure
    0 references
    correlation polytope
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references