Abstract: A spin glass system may have many configurations of the same ground-state energy. When the spins on some of the vertices have the same value among all the ground-state configurations, these vertices are referred to as frozen. If the spins on some other vertices have different values in different configurations, these vertices are therefore unfrozen. We show in this work that two or more unfrozen vertices may be prohibited from taking a certain combination of spin values, even though the spin of each vertex can fluctuate amongst different ground-state configurations. This phenomenon is called long-range frustration. We present a new long-range frustration order parameter R to quantify this phenomenon, and apply our mean field theory to the minimum vertex-cover problem and the random K-satisfiability problem.