text:
\section{Introduction}

An attempt was made in a recent paper \cite{ZhouH2004b} to study the
vertex cover problem from the viewpoint of long range frustration.
The vertex cover problem, sometimes also referred to as the hard--core gas
condensation problem in the physics literature,  can be mapped to a
spin glass model with quenched randomness coming from the underlying
random vertex--vertex connection patterns.
In the present paper, we extend the basic idea and the
method of Ref.~\cite{ZhouH2004b} to spin glass systems with an
additional kind of quenched randomness due to the random couplings
among interacting vertices. We demonstrate our calculations by working
on a spin glass model of the random $K$-satisfiability ($K$-SAT) problem.
Our results will be compared with known algorithmic and analytical conclusions.

The $K$-SAT is at the root of computational
complexity \cite{GareyM1979}. A $K$-SAT formula involves $N$ Boolean variables
and $M= \alpha N$ constraints or clauses, each of which is a disjunction of $K$ Boolean
variables or their negations. The parameter $\alpha$ is called the
clauses-to-variables ratio. A $K$-SAT formula is satisfiable (SAT) if there
exists at least one assignment of the Boolean variables
(a solution) such that all clauses are
satisfied; otherwise it is unsatisfiable (UNSAT). For example, the $2$-SAT
formula
$$
(x_1 \lor \bar{x_2}) \land (x_1 \lor x_2)
\land (\bar{x_1}\lor x_3)\land (x_2\lor \bar{x_3})
$$
with $N=3$ and $M=4$ has a SAT solution of  $x_1=x_2=x_3={\tt TRUE}$.
Given a $K$-SAT formula, the
objective is to judge whether it is satisfiable or not, and if it is,
to find a satisfying solution.
The satisfiability of a $2$-SAT formula can be determined
in a run time that scales linearly with the number $N$ of
Boolean variables \cite{AspvallB1979}. However, to determine the
satisfiability of a $K$-SAT formula with $K \geq 3$
is NP-complete, with a computation time that
scales {\em exponentially} with $N$ in the worst case.
The reason for this qualitative difference in computational complexity
is still not completely clear.

When a $K$-SAT formula of $N$ variables and $M$ clauses is chosen randomly
from the ensemble of all such formulas,
it was observed  \cite{CheesemanP1991,KirkpatrickS1994,CrawfordJ1996} that
its probability $p$ of being
satisfiable drops from $p\approx 1$ to $p\approx 0$ over a small range of the
parameter $\alpha$ around certain
$\alpha_c$ (for $K=3$, $\alpha_c \approx 4.2$
\cite{KirkpatrickS1994,CrawfordJ1996,AchlioptasD2001}).
Furthermore, although the $K$-SAT problem ($K\geq 3$) in general
is NP-complete,
the satisfiability of a randomly chosen formula can often be
easily determined by a heuristic algorithm, provided that its
parameter $\alpha$ is {\em not} at the
vicinity of the SAT-UNSAT transition point $\alpha_c$.
The really difficult instances of random $K$-SAT ($K\geq 3$) are
located at the parameter regime of $\alpha \approx \alpha_c$ \cite{CheesemanP1991}.

The above mentioned threshold phenomena are reminiscent of
what is usually observed in a physical system around
its phase transition or critical point. Concepts of
spin glass physics, such as replica symmetry breaking
and proliferation of metastable states, were  applied to the random
$K$-SAT problem in some recent articles
\cite{MonassonR1996,MonassonR1997,MonassonR1999,MezardM2002,MezardM2002b}.
For the random $3$-SAT problem, M{\'{e}}zard and co-authors
\cite{MezardM2002,MezardM2002b} found that in the parameter regime
of $3.921 < \alpha < 4.267$, there exists a hard-SAT phase with positive
structural entropy (complexity). A random $3$-SAT formula in this
phase is satisfiable by exponentially many Boolean configurations,
which are clustered
into different macroscopic domains. There are also exponentially
many metastable domains of configurations which satisfy most but not
all the clauses (a local search algorithm is likely to be trapped in
one of these metastable configurational domains).
This physical insight is implemented
in an efficient  heuristic
survey propagation algorithm \cite{BraunsteinA2002}
to find a solution for a random $3$-SAT formula.

Trying to understand more deeply the qualitative
difference between the $2$-SAT and the general
$K$-SAT problem ($K \geq 3$),
in this paper we re-examine the random $2$-SAT and
$3$-SAT problem by focusing on the issue of long range frustration
among unfrozen
Boolean variables.
A long range frustration order parameter $R$ is calculated.
We find that, while the SAT--UNSAT transition occurs at
$\alpha_c(2)=1$ for the random $2$-SAT problem,
long range frustration only gradually builds up when
$\alpha \geq \alpha_R(2) = 4.4588$, where
the non-frustrated mean field solution becomes unstable.
For the random $3$-SAT problem, we find a self-consistent
long--range frustrated solution when $\alpha \geq \alpha_R(3)= 4.189724$.
The long range frustration
order parameter $R$ of this solution jumps from zero to
a finite positive value at $\alpha_R(3)$, while the energy density
increases only gradually from zero as a function of $\alpha$.
This solution predicts that the SAT-UNSAT transition occurs
at $\alpha = \alpha_R(3)$.
However, for the random $3$-SAT problem, the non-frustrated
trivial mean field solution is stable even when $\alpha > \alpha_R(3)$;
and furthermore, in the range of $3.921 < \alpha < 4.267$ there is
a non-frustrated replica symmetry breaking solution of
zero energy \cite{MezardM2002b}. It is likely that the
true SAT-UNSAT transition point is at $\alpha = \alpha_c(3) = 4.267$.
Two possible reasons for this discrepancy between our mean field
solution and the solution of Ref.~\cite{MezardM2002b}
are discussed in this paper.
It appears that, when the replica symmetry breaking occurs
before the onset of long range frustration, the method outlined
in this paper needs to be improved, and competitions
among different macroscopic states should be considered
in the mean field theory.
More work is certainly needed to overcome this discrepancy.

This paper is organized as follows.
We first define the random $K$-SAT
problem in Sec.~\ref{sec:model}. The random $2$-SAT problem
and the $\pm J$ Viana--Bray spin glass model are
then studied in Sec.~\ref{sec:2}.  The method developed in
this section is then applied to the more difficult
random $3$-SAT problem in Sec.~\ref{sec:3}.
We summarize and discuss our main results in Sec.~\ref{sec:4}.

                                %

                                %

\section{
  Spin glass model of the random $K$-satisfiability problem
  \label{sec:model}
}

We follow Ref.~\cite{MezardM2002} and represent a random $K$-SAT formula
by a random factor graph
of $N$ variable nodes and $M=\alpha N$
function nodes. Each variable node $i$ represents a Boolean variable,
with a spin value $\sigma_i= \pm 1$.  It is connected to $k$ function nodes,
where $k$ is a random integer governed by the Poisson distribution
$f(k, c)$ of mean $c = K \alpha$. The Poisson distribution is defined as
\begin{equation}
  \label{eq:poisson}
  f( k , c ) ={ e^{-c} c^k  \over k !} \ .
\end{equation}
Each function node $a$ represents
a clause (constraint); it is linked to $K$ randomly chosen
variable nodes  $i_1,\ldots, i_K$. Function node $a$ has an
energy $E_a$ which is either $0$ (clause satisfied) or $1$ (clause
violated):
\begin{equation}
  E_a= \prod\limits_{r=1}^K {1-J_{a}^{i_r} \sigma_{i_r} \over 2} \  ,
  \label{eq:01}
\end{equation}
where $J_{a}^{i_r}$ is the edge strength between
$a$ and $i_r$:
$J_{a}^{i_r}=-1$ or $1$ depending on whether
Boolean variable $i_r$ in clause $a$ is negated or not.
In a given  random $K$-SAT formula, $J_{a}^{i_r}$ is  a
quenched random variable with value equally
distributed over  $\pm  1$.  The total energy of the system for
each of the $2^N$ possible spin configurations is
expressed as
\begin{equation}
  \label{eq:totalenergy}
  E[\{ \sigma_i  \}]=\sum\limits_{a=1}^{M} E_a \ .
\end{equation}
As we are interested in the ground--state energy landscape of
model Eq.~(\ref{eq:totalenergy}), only
those configurations which have the global minimum energy are
considered in later discussions.

                                %

                                %

\section{
  The random $2$-satisfiability problem and the $\pm J$
  Viana--Bray spin glass  model
  \label{sec:2}
}

We begin with the random $2$-SAT problem. Experience gained
in this section
will help us to understand the more difficult random $3$-SAT
problem in the next section.
We discuss the random $2$-SAT problem first
from the viewpoint of long range frustration
(Sec.~\ref{sec:2a}). Then we study it in
Sec.~\ref{sec:2b} through the cavity method of M{\'{e}}zard and
Parisi \cite{MezardM2001,MezardM2003} by setting the
long range frustration order parameter to $R=0$.
The later treatment
causes  an annoying divergence in the population dynamics, suggesting
the necessity of taking into account the effect of
long range frustration.
In Sec.~\ref{sec:2c} we briefly discuss the
finite connectivity $\pm  J$ Viana--Bray spin glass model.

\subsection{
  Long range frustration in a single macroscopic state
  \label{sec:2a}
}

The ground--state configurations of a random $2$-SAT formula
may be classified into different macroscopic states
\cite{MezardM2003} (hereafter, a macroscopic state is
simply referred to as a state).
Two microscopic configurations in the same state are mutually reachable by
flipping a  finite number of spins
of one configuration and then
letting the system relax. According to this definition of
states, two configurations of the same state
may differ from each other in the spin values of $O(N)$ variable
nodes (this is due to the formation of a percolation cluster
of unfrozen variable nodes discussed later).
We focus on a randomly chosen macroscopic
state $\beta$. In state $\beta$,  the spin value of a randomly chosen
variable node $i$ may be
fixed to $\sigma_i \equiv +1$ (positively frozen), or to $\sigma_i \equiv -1$
(negatively frozen), or fluctuate over  $\pm 1$ (unfrozen).
The fraction of positively frozen, negatively
frozen, and unfrozen variable nodes in state $\beta$ is, respectively,
$q_{+}$, $q_{-}$, and $q_{0}$, with $q_{+} + q_{-} + q_{0} = 1$.
Our approach at the present stage is essentially replica symmetric
because of the following reasons:
(a) although many macroscopic states may coexist, our system is
assumed to stay always in the same state,(b) a state is
characterized by just two mean field parameters, $q_0$ and $R$
(to be defined later).

Since the spin values of the unfrozen variable nodes fluctuate among
different configurations of state $\beta$, the possibility of correlation
among these fluctuations must be
taken into account.  Consider an unfrozen variable node $i$.
If its spin value is externally
fixed to a prescribed value $\sigma_i = \sigma_i^*$ ($\sigma_i^*=\pm
1$ with equal probability),
how many other unfrozen variable nodes must
eventually fix their spins as a consequence?

For a random factor graph with size $N \to \infty $,
the total number $s$ of affected variable nodes may scale linearly
with $N$ and therefore also approaches infinity.
If this happens, $\sigma_i^*$ is referred to as a canalizing value for
variable node $i$, and variable node $i$ is referred to as
type-I unfrozen with respect to spin value $\sigma_i^*$.
This happens with probability
$R$, with $R$ being our long range frustration order parameter.
The total number of affected variable nodes may also be finite,
$s\sim O(1)$.
In this case, variable node $i$ is  type-II unfrozen
with respect to spin value $\sigma_i^*$.
We emphasize that, if an unfrozen
variable node $i$ is type-I unfrozen with respect to spin
value say $\sigma_i=+1$, it is not necessarily also
type-I unfrozen with respect to spin value $\sigma_i=-1$;
in other words, the fact that $\sigma_i^*$ is a canalyzing value for
variable node $i$ does not mean that $-\sigma_i^*$ is also
a canalyzing value for the same node. In the remaining part of
this article, to simplify the notation,
we will frequently use phrases such as
$``$variable node $i$ is type-I unfrozen'' and
$``$a type-II unfrozen variable node $i$''.
It should be understood that, whenever we mention that
a variable node $i$ is type-I or type-II unfrozen, we
mean that it is type-I or type-II unfrozen
with respect to a prescribed spin value $\sigma_i^*$.

Based on the bond percolation theory on random graphs
\cite{BollobasB1985}, we know that the
percolation clusters evoked by two type-I unfrozen variable nodes
have a nonzero intersection of size proportional to $N$.
Therefore, the spin values of all type-I unfrozen variable nodes
must be strongly correlated. If we randomly choose two
type-I unfrozen variable nodes $i$ and $j$,
then with probability {\em one half}
$\sigma_i^*$ and $\sigma_j^*$  can not be realized simultaneously
in any configuration of state $\beta$:
if $\sigma_i=\sigma_i^*$, then $\sigma_j$ must take
the value $\sigma_j=-\sigma_j^*$;
if $\sigma_j=\sigma_j^*$, then $\sigma_i$ must take the value
$\sigma_i=-\sigma_i^*$.
The probability one half comes from the fact that both $\sigma_i^*$
and $\sigma_j^*$ are
random variables equally distributed over  $\pm  1$ (due to the quenched
randomness in the edge strengths, as will become clear later).
On the other hand, two randomly chosen type-II unfrozen
variable nodes are mutually independent, since each of them can only
influence the spin values of $s \sim O(1)$ other variable
nodes while the shortest path length between them scales as $\ln N$
\cite{BollobasB1985}.
For later convenience, we denote $F(s)$ as the probability that a
randomly chosen unfrozen
variable node $i$ will eventually fix a total number $s$ of
other unfrozen variable nodes when it is flipped to a prescribed value
$\sigma_i= \sigma_i^*$,
where $s$ is under the constraint that $s\sim O(1)$ and
therefore $\lim_{N\to \infty} s/N=0$.

We follow the cavity field approach to calculate the parameters $q_{+}$, $q_{-}$,
and $q_{0}$.  We first generate a random factor graph $G$ of $N$ variable nodes and
(on average) $\alpha N$ function nodes.
Then we create a new variable node $i$ and connect it to
$G$ by a set $V_i$ of new function nodes, the size $k$ of this set
following the Poisson distribution $f(k, 2 \alpha)$.
Each of these newly constructed function nodes is connected
to a randomly chosen variable node of $G$ at its other end.
The enlarged factor graph is denoted as $G^\prime$.
It has $N+1$ variable nodes and on average
$\alpha N + 2 \alpha$ function nodes.

We look at the local environment of a newly added
function node $a$, which is connected to the new variable node $i$ and
a randomly chosen variable node $j$ of factor graph $G$.
Let us denote $\sigma_j^* = J_a^j$.
In factor graph $G$ variable node $j$ may be frozen to the spin value  $\sigma_j^*$ or
to $-\sigma_j^*$, it may also be unfrozen.
Now we ask the question:  Can function node $a$  be satisfied by variable
node $j$ alone? There are the following possibilities:

\begin{description}
\item[(i).]
  Node $j$ is frozen in factor graph $G$ to $\sigma_j\equiv \sigma_j^*$.
  This happens with probability $(q_{+} + q_{-})/2 = ( 1- q_0 ) / 2$.
  In this situation, function node $a$ is satisfied.

\item[(ii).]
  Node $j$ is unfrozen and $\sigma_j^*$ is not a canalizing value of
  node $j$ (type-II unfrozen).
  This happens with probability $ q_0 ( 1 - R)$.
  In this situation, function node $a$ is also satisfiable
  by flipping $\sigma_j$ to the value $\sigma_j^*$.

\item[(iii).]
  Node $j$ is unfrozen and $\sigma_j^*$ is a canalizing value of node
  $j$ (type-I unfrozen).
  This happens with probability $ q_0 R$.
  In this situation,
  function node $a$ is  also satisfiable by flipping $\sigma_j$ to
  the value $\sigma_j^*$.
  However,  this spin flip will evoke a  percolation cluster
  (with size scaling linearly with $N$) of unfrozen variable nodes,
  namely, the spin values of these unfrozen variable nodes
  all have to be fixed.

\item[(iv).]
  Node $j$ is frozen to $\sigma_j=-\sigma_j^*$.
  This happens with probability $(q_{+} + q_{-})/2 = ( 1 - q_0 ) / 2 $.
  In this situation, function node $a$ is unsatisfiable by node $j$.
  To  satisfy $a$, variable node $i$ must be fixed to the
  value $\sigma_i = J_{a}^i$.
\end{description}

In the set $V_i$, a number $k_{iii}^{+}$  of function nodes,
each connected to variable node $i$ by a positive bond,
are facing the local environment described by the above--mentioned
situation (iii).
The random integer $k_{iii}^{+}$ is governed by the Poisson
distribution $f( k_{iii}^{+}, \lambda_1 )$, where
$\lambda_1 = \alpha q_0 R$. When $\sigma_i$ is set to
$\sigma_i=-1$, these function nodes are not satisfied by node $i$. To
satisfy them, the $k_{iii}^{+}$
unfrozen variable nodes attached to the other ends of
these function nodes must all be flipped to the appropriate spin values.
However, since each such spin flips will lead to a
percolation cluster of size approaching infinity,
these function nodes may not all be
simultaneously satisfiable
due to the possibility of long range frustration among
the type-I unfrozen variable nodes.
These $k_{iii}^{+}$ type-I unfrozen variable nodes can be divided into
two subgroups (say $S_A$ and $S_B$); variable nodes of the same subgroup can take
their canalyzing
spin values simultaneously in state $\beta$, while variable nodes from
different subgroups will never take their corresponding
canalyzing spin values simultaneously in state $\beta$.
Because all these $k_{iii}^{+}$ variable nodes are
unfrozen, their spin values for sure will fluctuate among different
miscroscopic configurations. Therefore, in some microscopic configurations,
variable nodes in $S_A$ will take their canalyzing spin values; and in
some other microscopic configruations, variable nodes in $S_B$ will
take their canalyzing spin values.
When the spin value of variable node $i$ is set to $\sigma_i=-1$,
the probability $P_{\rm f}(n)$ that at least $n$ function nodes will
be unsatisfied due to this type of long range frustration can be expressed as
\begin{equation}
  P_{\rm f}(n) =  f( 2 n , \lambda_1 ) \ C_{2n}^{n}\  2^{- 2 n} +
  \sum\limits_{n^\prime=2 n +1}^{\infty} f(n^\prime,  \lambda_1 )
  \ C_{n^\prime}^{n} \  2^{1-n^\prime} \ ,
  \label{eq:05}
\end{equation}
where $C_{n^\prime}^{n}=n^\prime ! / ( n ! (n^\prime -n)!)$ is the binomial
coefficient.
The first term on the right hand side of
Eq.~(\ref{eq:05}) corresponds to the case that
the above-mentioned two subgroups have the
same size $n$ ($k_{iii}^{+}= 2n$); the second term  corresponds to
the case that these two subgroups are not equal in size,
one containing $n$ variable nodes and the other containing
more than $n$ variable nodes ($k_{iii}^{+} \geq 2 n +1$).

In the set $V_i$ of function nodes, $k_{iv}^{+}$ of them are
connected to $i$ by a positive bond and are facing the local
environment (iv). The random value $k_{iv}^{+}$ is governed
by the Poisson distribution
$f( k_{iv}^{+},  \lambda_2 )$, with
$\lambda_2 = \alpha ( 1 - q_0 )/2$.  These function nodes are
definitely unsatisfied when $\sigma_i = -1$.
Therefore, the probability $P_{\rm v}(m_{-})$
that $m_{-}$ function nodes will be unsatisfied when $\sigma_i = -1$ is
\begin{equation}
  \label{eq:04}
  P_{\rm v}(m_{-})=\sum\limits_{n=0}^{m_{-}}
  f\bigl( n , \lambda_2  \bigr) \  P_{\rm f}(m_{-} - n) \ .
\end{equation}

When $\sigma_i$ is set to $\sigma_i = +1$, $m_{+}$ function nodes
in the set $V_i$ may be unsatisfied.
It is easy to verify that
$m_{+}$ follows the same probability distribution as $m_{-}$.
Since the probability distributions for $m_{+}$ and $m_{-}$ are
known, the probability $q_0(i)$ for variable node $i$ to be
unfrozen in the corresponding state $\beta^\prime$ of
the enlarged graph $G^\prime$ can be
calculated. In the large $N$ limit, we assume the following
convergence condition that
\begin{equation}
  \lim\limits_{N\to \infty} q_0(i) = q_0 \ .
  \label{limit}
\end{equation}
With this assumption, we can therefore
write down the following self-consistent equation
for  the parameter $q_0$:
\begin{equation}
  q_0 = \sum\limits_{m_{+}=0}^{\infty} \sum\limits_{m_{-}=0}^\infty
  P_{\rm v} (m_{+})\  P_{\rm v}(m_{-}) \ \delta_{m_{+}}^{m_{-}} \ ,
  \label{eq:06}
\end{equation}
where $\delta$ is the Kronecker symbol.
It is easy to verify that $q_{+} = q_{-} = (1 - q_0 ) / 2$.

We make an important remark here. At the present stage of the
mean field theory, we focus only on one state $\beta$ of
factor graph $G$, and assume
that Eq.~(\ref{limit}) holds in this state $\beta$.
When the system has more than one state, there may be
competitions among these different states. As an example
of such competitions, consider two
states $\beta_1$ and $\beta_2$ of factor graph $G$.
We assume $\beta_1$ is a ground state and $\beta_2$ is a ground state or
metastable state, therefore $E_1 \leq E_2$, where $E_{1}$
($E_2$) is
the energy of factor graph $G$ in state $\beta_1$ $(\beta_2)$.
When the new variable node $i$ is added,
$n_1$ and $n_2$ of the nearest-neighbor function nodes of
$i$ may be violated in the two corresponding states $\beta_1^\prime$
and $\beta_2^\prime$ of
factor graph $G^\prime$. Therefore, $G^\prime$  have
energy $E_1^\prime= E_1 + n_1$ and $E_2^\prime=E_2 + n_2$, respectively,
in state $\beta_1^\prime$ and $\beta_2^\prime$. We see that, although
$E_1 \leq E_2$, in the enlarged system state $\beta_2^\prime$  may
have lower energy than state $\beta_1^\prime$ if
$n_1 - n_2 > E_2 - E_1$. To correctly predict the
ground state energy of the enlarged system $G^\prime$, we
may need the information on all the low energy states of
the original system $G$. We hope to return to this
point in a future work. In the present paper, we stick
to one state $\beta$ of factor graph $G$.

Now we calculate the order parameter $R$. Suppose in state $\beta$
variable node
$i$ is unfrozen, and it is type-II unfrozen with respect
to the spin value, say, $\sigma_i = -1$. That is, flipping the spin value of
node $i$ to $\sigma_i = -1$ will cause the fixation of
the spin values
of $s\sim O(1)$ other unfrozen variable nodes. Then all the function nodes
that are connected to $i$ by a positive bond should not face the
above--mentioned local environment  (iii) but may face the local
environment (ii). Consider such a function node $a$, and suppose
its other end is connected to a type-II unfrozen variable node $j$
by  a positive bond (the discussion is the same if the bond is
negative).
When the spin value of variable node $i$ is set to $\sigma_i = -1$,
the spin value of node $j$ must be
flipped to $\sigma_j = +1$
to satisfy function node $a$.
On the other hand, variable node $j$
may be connected to other function nodes besides node $a$; and
therefore when $\sigma_j$ is set to $\sigma_j=+1$, some other
type-II unfrozen variable nodes will be affected, $\ldots$
(a $``$chain reaction").
Based on  this observation,
the probability distribution $F(s)$ defined earlier in this subsection
can be determined by the following iterative equation:
\begin{equation}
  F(s)  =  f\bigl(0,  \lambda_3 \bigr) \  \delta_{s}^{0} \ +
  \sum\limits_{k=1}^{\infty} f\bigl( k , \lambda_3 \bigr)
  \sum\limits_{\{s_l \}}
  \delta_{s_1+\ldots +s_k }^{s} \prod\limits_{l=1}^{k} F(s_l)\ ,
  \label{eq:02}
\end{equation}
where $\lambda_3 = \alpha q_0 ( 1 - R )$ is the average
number of function nodes that are attached to variable node
$i$ by a positive bond and are facing the above mentioned
local environment (ii).
Equation~(\ref{eq:02}) holds true as long as the cluster of
affected variable nodes forms a tree, i.e., there is no loops.
This constraint is satisfied in a random factor graph
of size $N\to \infty$, since the shortest loop
length between two variable nodes scales as $\ln N$
\cite{BollobasB1985} while the cluster size $s$ scales
as $O(1)$.

Since $R=1-\sum_{s=0}^\infty F(s)$, from Eq.~(\ref{eq:02}) we realize that
\begin{equation}
  R=1- \exp\bigl(-  \lambda_3 R \bigr) \ .
  \label{eq:03}
\end{equation}

\begin{figure}[t]

  \psfig{file=figure02.ps,angle=270,width=10.0cm}
  \caption{ \label{fig:02}
    The long range frustration order parameter $R$ (solid lines) and
    the unfrozen probability $q_0$ (dashed lines) as a function
    of $\alpha$ for the
    random $2$-SAT problem.
    The inset is an amplification of the region of
    $ \alpha \in [0 , 10]$.
  }
\end{figure}

The unfrozen probability $q_0$ and the long range frustration order
parameter $R$, as calculated by Eqs.~(\ref{eq:06}) and (\ref{eq:03}),
are shown in Fig.~\ref{fig:02} as a function of
the clauses-to-variables ratio $\alpha$.  Onset of spin freeze occurs at
$\alpha = \alpha_c(2) = 1$. This point, as shown later, is also the point of
SAT--UNSAT transition, in agreement with the
rigorous mathematical proof \cite{FernandezW2001}.
A typical random $2$-SAT formula of $\alpha < 1$ is
satisfiable while a typical random $2$-SAT formula of $\alpha > 1$ is
unsatisfiable. However, onset of long range frustration is delayed
to $\alpha = \alpha_R(2) = 4.4588$.
For $\alpha_c(2) < \alpha < \alpha_R(2)$ a typical random
$2$-SAT formula, although being unsatisfiable, is not long--range
frustrated.
We know that to determine the satisfiability of a $2$-SAT formula is
computationally easy. It is interesting to
point out that,  long range
frustration is absent at {\em both} sides of
the SAT-UNSAT transition $\alpha_c(2)$ for the random $2$-SAT problem.

Based on our calculation that a randomly constructed $2$-SAT formula
in the parameter regime of $\alpha_c(2) < \alpha < \alpha_R(2)$ is
not long--range frustrated ($R=0$),
we hope that a Boolean assignment that
satisfies the largest possible number of its clauses
might be easily found in practice, despite the fact
that the MAX-$2$-SAT problem is in general
NP-hard \cite{FernandezW2001}.
We will check this point by computer
simulations in a later work.

When $\alpha \geq \alpha_R(2)$, long range frustrations exist among a
fraction of
the unfrozen variable nodes. Interestingly, the point
$\alpha= \alpha_R(2)$ also marks the
beginning of divergence of the population dynamics of the next
subsection.

Now we turn to the ground--state energy density $\epsilon$. The
energy increase $\epsilon_{1}$ due to the addition of variable node $i$ is
\begin{equation}
  \epsilon_1 (\alpha) = \sum\limits_{m_{+}=0}^\infty
  \sum\limits_{m_{-}=0}^\infty P_{\rm v}(m_{+}) \
  P_{\rm v}(m_{-}) \  \min( m_{+}, m_{-} ) \ .
  \label{eq:07}
\end{equation}
After the addition of variable node $i$, the factor graph $G^\prime$
has $N+1$ variable nodes and on average $\alpha N + K \alpha$ function nodes
($K = 2$).
Its clauses-to-variables ratio is therefore
$\alpha^\prime = \alpha + (K-1) \alpha / (N+1)$. Suppose the energy
density $\epsilon$ of the system is
a function only of $\alpha$. Then from the identity
$$
(N+1) \epsilon( \alpha^\prime )  = N \epsilon( \alpha )
+ \epsilon_1 \ ,
$$
we obtain the following differential equation
$$
\epsilon( \alpha ) + ( K - 1 ) \alpha
{ {\rm d} \epsilon \over {\rm d} \alpha } = \epsilon_1
$$
in the limit of large $N$. By solving this differential
equation, we obtain that
\begin{equation}
  \epsilon(\alpha)= { 1 \over ( K-1) \alpha^{1/(K-1)} }
   \int_{0}^{\alpha} \tilde{\alpha}^{{2-K \over K-1 } }
   \epsilon_1( \tilde{\alpha} ) {\rm d} \tilde{\alpha} \ ,
  \label{eq:08}
\end{equation}
where $K=2$.
According to the author's unpublished calculations,
in the vertex cover problem, the energy density derived through this
way is the exact ground--state energy density when there is
no long range frustration; however, when $R > 0$,
this energy density is  lower than the
actual ground--state energy density obtained
by Weigt and Hartmann by numerical means \cite{WeigtM2000}
(the reason, however, is still
unknown). We expect the same situation will
occur here in the random $K$-SAT problem.

When long range frustration exists ($R > 0$), an upper bound for
the ground--state energy density $\epsilon$ can also be derived.
For the enlarged factor graph $G^\prime$ to have clauses-to-variables
ratio  $\alpha$,
on average $(K-1) \alpha$ function nodes must be removed
\cite{MezardM2003}. The energetic contribution
of these function nodes must also be removed. This contribution
comes from two parts: (i) the energy sum of these individual function nodes,
$\Delta E= (K-1) \alpha [(1-q_0)/2]^K$ and, (ii)
additional energy $\Delta E^\prime$ caused by  possible
long range frustration among  these function nodes. Therefore,
\begin{equation}
  \epsilon( \alpha ) = \epsilon_1 - \Delta E - \Delta E^\prime.
  \label{eq:09}
\end{equation}
If we set $\Delta E^\prime =0$, Eq.~(\ref{eq:09}) then gives an upper bound.

The energy densities calculated based on Eqs.~(\ref{eq:08}) and (\ref{eq:09})
are shown in Fig.~\ref{fig:03}. When $\alpha > \alpha_c(2)$, the energy density
becomes positive and the system is UNSAT.  In the range of
$\alpha_c(2) \leq \alpha < \alpha_R(2)$,
both Eq.~(\ref{eq:08}) and (\ref{eq:09}) give the identical results,
indicating that when there is no long range frustration, these equations
are exact. When $\alpha \geq \alpha_R(2)$, the energy density given
by Eq.~(\ref{eq:09}) is
systematically higher than that given by Eq.~(\ref{eq:08}). In this regime of
long range frustration,   at the moment
the author is still unable to give an exact
ground--state energy density expression. We hope to return to this point
in a future work.

\begin{figure}[t]

  \psfig{file=figure03.ps,angle=270,width=10.0cm}
  \caption{ \label{fig:03}
    The energy density lower bound (solid lines) and
    upper bound (dashed lines) for the random $2$-SAT and
    $3$-SAT problem as a function of $\alpha$.
  }
\end{figure}

\subsection{
  Random $2$-satisfiability studied by population dynamics
  \label{sec:2b}
}

In this subsection, we study the random $2$-SAT problem
following the zero--temperature cavity method treatment
of Ref.~\cite{MezardM2002b}. Since in the parameter
range of $0 \leq \alpha < \alpha_R(2)$ there is
no long range frustration, we expect this treatment to
be exact in this range.

Suppose there are many macroscopic states of global
minimum  energy.
Let us randomly choose a function node $a$ and
follow one of its edges to a variable node $i$. Before the
edge $(a, i)$ is connected, variable node
$i$ may be positively frozen in some macroscopic states,
and be negatively frozen in some other macroscopic states,
and be unfrozen in the remaining macroscopic states.
A positively (negatively) frozen variable node is said to feel a
positive (negative) cavity field $h_i$, while an unfrozen
variable node is said to feel a zero cavity
field $h_i$ \cite{MezardM2003}.
The (modified) cavity field $J_a^i h_i$ distribution among all
the macroscopic states
(referred to as the cavity field survey)
is denoted by $P( J_a^i h_i )$, where $J_a^i$ is the
bond strength between function node $a$ and variable node $i$.
Besides function node $a$, node  $i$ is connected by
positive bonds to $p$ other function nodes $b_1 , \ldots , b_p$ and
by negative bonds to $n$ other function nodes $c_1 , \ldots , c_n$.

Assuming there is no long range frustration among the unfrozen
variable nodes ($R=0$), one can write down the following self-consistent
equation for the cavity field distribution $P(J_a^i h_i)$
\cite{BraunsteinA2002}:
\begin{eqnarray}
  P(J_a^i h_i) &
  \propto & \int \bigl[ \prod\limits_{r=1}^{p} P( J_{b_r}^{j_r} h_{j_r} )
  {\rm d} h_{j_r} \bigr]
  \bigl[ \prod\limits_{l=1}^{n} P( J_{c_l}^{k_l} h_{k_l} )
  {\rm d} h_{k_l} \bigr] \times \nonumber \\
  & &
  \delta\bigl(
  J_a^i h_i - \sum\limits_{r=1}^{p} \theta(-J_{b_r}^{j_r} h_{j_r}
  \bigr)
  + \sum\limits_{l=1}^n \theta(-J_{c_l}^{k_l} h_{k_l} ) ) \times \nonumber \\
  & & \exp(-y \Delta E_1 /2 )
  \label{eq:survey}
\end{eqnarray}
where $\theta(x)$ is the Heaviside step function, $\theta(x)=1$ if
$x >0$ and $\theta(x)=0$ otherwise; $y$ is a re-weighting parameter;
and
\begin{eqnarray}
  \Delta E_1 &=&
  \sum_{r=1}^p \theta(-J_{a_r}^{j_r} h_{j_r} )
  + \sum_{l=1}^n \theta(-J_{b_l}^{k_l} h_{k_l}) \nonumber \\
  & &
  - |\sum_{r=1}^p \theta(-J_{a_r}^{j_r} h_{j_r} )
  - \sum_{l=1}^n \theta(-J_{b_l}^{k_l} h_{k_l}) |
  \label{eq:d_E_1}
\end{eqnarray}
is twice the energy caused by the function nodes $b_1,\ldots, b_p,
c_1,\ldots, c_n$.

In the limit of $y\to +\infty$,
the general form of the cavity field distribution is \cite{BraunsteinA2002}
\begin{equation}
  P( J_a^i h_i ) =
  \left\{
    \begin{array}{ll}
      P_{+}( J_a^i h_i)\ , &  p_+ \\
      P_{-}( J_a^i h_i)\ , &  p_- \\
      \begin{array}{r}
        \eta_0(i) \delta( J_a^i h_i ) + \eta_+(i) P_{+}( J_a^i h_i )
        \\
        + \eta_-(i) P_{-}( J_a^i h_i )\ .
      \end{array} & p_0
    \end{array}
  \right.
  \label{eq:survey_form}
\end{equation}
In Eq.~(\ref{eq:survey_form}), $p_{+}$, $p_{-}$, and $p_0$ are the
probabilities of occurrence for the three types of cavity field
surveys. $P_{+}(k)$ is a probability distribution over
positive integers $k$; and $P_{-}(k)$ is a probability distribution
over  negative integers $k$. The parameters $\eta_0(i)$,
$\eta_{+}(i)$, and $\eta_{-}(i)$ are three random variables,
$\eta_{0}(i)+\eta_{+}(i)+\eta_{-}(i)=1$.

Based on Eqs.~(\ref{eq:survey}) and (\ref{eq:survey_form}),
one finds that
\begin{eqnarray}
  p_0 = \sum\limits_{m=0}^\infty
  {  e^{- \alpha ( 1 - p_0 ) } \bigl( \alpha ( 1 - p_0 ) / 2 \bigr)^{2 m}
    \over ( m! )^2 } \ ,
  \label{eq:p_0} \\
  p_+ = p_- = ( 1 - p_0 ) / 2 \ .
  \label{eq:p+}
\end{eqnarray}

When $\alpha \leq  \alpha_R(2)$, the probability $p_0$ satisfies
$\alpha p_0 \leq 1$.  Consequently,
the population dynamics at $y=\infty$ converges to the
replica symmetric fix point of $\eta_{0}\equiv 1, \eta_{+} =\eta_{-}\equiv 0$.
In other words, the system has only one macroscopic state.
When $\alpha > \alpha_R(2)$, this replica symmetric fixed point
is unstable, and if initially the random variables $\eta_{0}(i)$ are
slightly less than unity,
the population dynamics at $y=\infty$ becomes divergent.
This divergence suggests that, at this parameter regime,
the assumption of absence of long range frustration becomes
invalid.

To get rid of this divergence,
one can run population dynamics at a finite positive value
of $y$. A conceptually
better way is to directly take into account the
effect of long range frustration in the population dynamics.
Unfortunately, at the moment the author is
unable to achieve this goal.

\subsection{
  The $\pm J$ Viana--Bray spin glass model
  \label{sec:2c}
}

We now briefly discuss the zero temperature phase diagram of the
$\pm J$ Viana--Bray model \cite{VianaL1985}. The model is characterized
by the Hamiltonian
\begin{equation}
  \label{eq:10}
  E[\{ \sigma_i \}]= - \sum\limits_{(ij)} J_{i j} \sigma_i \sigma_j \ ,
\end{equation}
where the summation is over all the edges $(ij)$ of a Poisson random
graph of mean vertex degree $c$;  the edge strength $J_{ij}=\pm 1$,
with equal probability;
and $\sigma_i=\pm 1$ is the spin value on vertex $i$. The zero temperature
phase diagram of this model was first reported in Ref.~\cite{KanterI1987}
through the replica approach.
It was found that, when $c\leq  1$, the system is in the paramagnetic
phase with no frozen vertices, i.e., $q_0 = 1$; when $c >  1$,
the system is in the spin glass phase, where some vertices
are frozen to positive or negative
spin values, and $q_0$ gradually decreases from unity.

The Hamiltonian Eq.~(\ref{eq:10}) is similar to that of the random $2$-SAT and
can be studied by the same method mentioned in subsection \ref{sec:2a}.
We find that
the zero temperature phase diagram of model (\ref{eq:10}) is
identical to Fig.~\ref{fig:02} of the random $2$-SAT.
The transition between the
paramagnetic phase and the spin glass phase occurs at $c=1$, confirming the
earlier result of Ref.~\cite{KanterI1987}.
(When the long range frustration order parameter is set to
$R=0$, the order parameter $q_0$  has the same expression
as Eq.~(15) of Ref.~\cite{KanterI1987}.)
In the spin glass phase, long range frustration among unfrozen
vertices only builds up ($R > 0$) when the mean vertex
degree $c \geq 4.4588$.

The $\pm J$ finite connectivity spin glass model therefore has two types of
phase transitions as the mean connectivity is increased. First there is
the frozen transition to the spin glass phase; and then there is the
transition to a long--range frustrated spin glass phase.
It is more experimentally relevant to discuss the phase transitions in
terms of temperature. It is accepted that the spin glass phase will
persist over a finite temperature range of $0 \leq T < T_g$
\cite{VianaL1985}.
We expect that when the mean vertex degree $c > 4.4588$,
the long--range frustrated spin glass phase
will also persist over a temperature range of $0 \leq T < T_R$, with
$T_R \leq T_g$.  It will be of great interest to check the validity of
this picture by computer simulations.

Real world spin glass materials are three--dimensional, and their
spin--spin interactions may be more complex than that given by
Eq.~(\ref{eq:10}).
It is not known whether or not long range frustrations exist among the
unfrozen vertices of such systems, and if they do exist, how to
detect them experimentally. It may be useful to re-interprete
the already documented
experimental observations in terms of the long range frustration
order parameter $R$.

                                %

                                %

\section{
  The random $3$-satisfiability problem
  \label{sec:3}
}

This section focuses on the random $3$-SAT problem.
We study it using the method of Sec.~\ref{sec:2a} and then
compare the results with those obtained by population dynamics.

The probability of a randomly chosen variable node being
positively frozen, negatively frozen, or unfrozen in a
macroscopic state $\beta$ of global minimum energy is
denoted respectively as $q_{+}$, $q_{-}$, and $q_{0}$
as in the case of the random $2$-SAT problem. $R$ is the
probability that an unfrozen variable node is type-I
unfrozen with respect to a prescribed spin value.
The parameters $q_0$, $q_+$, $q_{-}$, and $R$
can be obtained following the same procedure as was outlined in
Sec.~\ref{sec:2a}.
We first generate a factor graph $G$ of $N$ variable nodes and
$M= \alpha N$ function nodes; we then create a new variable node $i$
and connect this new node $i$ to $G$ through the formation of
$k$ new function nodes, with $k$ following the Poisson distribution
$f(k, 3 \alpha)$. The other ends of such a function node $a$
are connected to two randomly chosen variable nodes $j$ and $k$
of the factor graph $G$.
For convenience of discussion, we denote $\sigma_j^* = J_a^j$ and
$\sigma_k^* = J_a^k$; and in the remaining part of this section,
when we mention that a variable node $j$ is type-I or type-II
unfrozen, we mean that it is type-I or type-II unfrozen with respect
to the spin value $\sigma_j^*$. In state $\beta$,
the function node $a$  faces one  of the
following local environments:
\begin{description}
\item[(i).]
  Node $j$ is frozen in factor graph $G$
  to $\sigma_j\equiv \sigma_j^*$ or
  node $k$ is frozen to $\sigma_k= \sigma_k^*$.
  This happens with probability $( 3 - 2 q_0 - q_0^2 ) / 4$.
  In this situation, function  node $a$ is satisfied by $j$
  or  $k$ (or both).

\item[(ii).]
  Both node $j$ and node $k$ are type-II unfrozen.
  This  happens with probability  $q_0^2 ( 1 - R )^2$.
  In this situation, function node $a$ is satisfiable by $j$ and $k$.

\item[(iii).]
  One of the two variable nodes, say $j$, is
  type-II unfrozen while the other, $k$, is type-I unfrozen.
  This happens with probability  $ 2 q_0^2  R ( 1 - R )$.
  In this situation, node $a$ is satisfiable by $j$.
  (It is also satisfiable by node $k$ through setting
  $\sigma_k = \sigma_k^*$, but this spin flipping will perturb
  the spin values of $O(N)$ other unfrozen variable nodes.)

\item[(iv).]
  Both node $j$ and node $k$ are type-I unfrozen, but they can not take
  the spin value $\sigma_j=\sigma_j^*$ and
  $\sigma_k=\sigma_k^*$ simultaneously in state $\beta$.
  This happens with probability   $ q_0^2 R^2 / 2$.
  In this situation, node $a$ is definitely satisfied by one of
  nodes $j$ and $k$ (in some configurations of $\beta$, node $j$
  satisfies $a$ while $\sigma_k = - \sigma_k^*$, and in the
  remaining configurations node $k$ satisfies $a$ while
  $\sigma_j= - \sigma_j^*$).

\item[(v)]
  Both node $j$ and node $k$ are type-I unfrozen and they can take
  the spin value $\sigma_j=\sigma_j^*$ and $\sigma_k=\sigma_k^*$
  simultaneously.   This happens with probability   $ q_0^2 R^2  /2$.
  In this situation, node $a$ is also satisfiable by $j$ and $k$.
  However, to satisfy  $a$ by node $j$ or $k$ will cause an extensive
  perturbation to the spin configuration,
  whereby the spin values of $O(N)$ other unfrozen variable nodes
  will eventually be fixed.

\item[(vi).]
  One of the variable nodes, say $j$, is type-I unfrozen while the other is
  frozen to $\sigma_k=-\sigma_k^*$. This happens with probability
  $2 q_0 q_{-} R$.
  In this situation, node $a$ is
  satisfiable by node $j$, with the same consequence as in situation (v).

\item[(vii).]
  One of the variable nodes, say $j$, is type-II unfrozen while the other
  is frozen to $\sigma_k=-\sigma_k^*$. This happens with probability
  $ 2 q_0 q_- ( 1 - R)$.
  In this situation, node $a$ is satisfiable  by node $j$.

\item[(viii).]
  Node $j$ is frozen to $\sigma_j=-\sigma_j^*$ and node $k$ is frozen to
  $\sigma_k=-\sigma_k^*$. This happens with probability $q_{-}^2$.
  In this situation, node $a$ is satisfiable only if
  the spin value of variable node $i$ is set to $\sigma_i= J_a^i$.
\end{description}

For the random $3$-SAT problem, the parameter $q_0$ is also determined
self-consistently by Eq.~(\ref{eq:06}), with the only difference
that $\lambda_1 = (3/2) \alpha [ q_0^2 R^2 /2 + 2 q_0 q_{-} R ]$ and
$\lambda_2 = (3/2) \alpha q_{-}^2$; and the parameter $R$ is
determined by Eq.~(\ref{eq:03}), with
$\lambda_3 = 3 \alpha q_0 q_{-} (1 - R)$.
The lower and upper bound of the global minimum energy density
can be obtained through Eqs.~(\ref{eq:08}) and (\ref{eq:09}), with
$K=3$.
The values of the long range frustration order parameter $R$ and the
fraction of unfrozen variable nodes  $q_0$ are shown in
Fig.~\ref{fig:01} as a function of $\alpha$,
and the energy density lower and upper bounds are
shown in Fig.~\ref{fig:03}.

\begin{figure}[t]

  \psfig{file=figure01.ps,angle=270,width=10.0cm}
  \caption{ \label{fig:01}
    Long range frustration index $R$ (circles) and
    fraction of unfrozen variables $q_0$ (squares) as
    a  function of clause-to-variable ratio $\alpha$ for
    the random $3$-SAT problem.
  }
\end{figure}

When $\alpha < \alpha_R(3)= 4.189724$, Eqs.~(\ref{eq:06}) and
(\ref{eq:03}) permit only a trivial solution of $q_0 \equiv 1$ and
$R \equiv 0$, with zero energy density. When
$\alpha \geq \alpha_R(3)$, this non-frustrated replica symmetric
solution is still locally stable.
However, at this parameter range, another stable self-consistent
solution appears. This nontrivial solution is long--range
frustrated, with its order parameter $R$ jumps from zero to
$R=0.2605$ at $\alpha= \alpha_R(3)$, accompanied by a drop of
$q_0$ from $q_0 =1$ to $q_0=0.5270$.
Interestingly, although there are jumps for the order parameters
$R$ and $q_0$ at $\alpha_R(3)$, the energy density of this
solution increases only {\em gradually} from zero as a function
of $\alpha$ (see Fig.~\ref{fig:03}).
This is an improvement over a previous mean field
solution. If long range frustration was not taken into
account, Eq.~(\ref{eq:06}) predicts a
nontrivial solution when $\alpha \geq 4.667$, which,
however, has an unphysical negative energy density as long as
$\alpha < 5.18$ \cite{MonassonR1996,MonassonR1997}.

The present mean field solution predicts that,
in the parameter range of $\alpha \geq \alpha_R(3)$
a random $3$-SAT formula will be long--range frustrated and
unsatisfiable.
This predicted SAT-UNSAT transition point is
located between the rigorously known lower and upper
bounds \cite{AchlioptasD2001}.
However,
through the zero temperature cavity method and population dynamics,
it is found in Ref.~\cite{MezardM2002b}
that, when $3.921 < \alpha < 4.267$
the random $3$-SAT problem has another non-frustrated
replica symmetry breaking solution with zero energy and
positive structural entropy. The structural entropy of
this non-frustrated solution becomes negative when
$\alpha \geq 4.267$, and this point is regarded as the
SAT-UNSAT transition point of the random $3$-SAT problem.
Therefore, there is a clear discrepancy between the present
work and the result of Ref.~\cite{MezardM2002b}.
Two reasons are conceivable for this discrepancy:

First, the treatment in this paper is essentially replica symmetric, with
only two order parameters $q_0$ and $R$. In the random $3$-SAT
problem, it is clear that replica symmetry breaking occurs before
the onset of long range frustration. This is different from what
happens in the random $2$-SAT problem of Sec.~\ref{sec:2}
and the vertex cover problem of Ref.~\cite{ZhouH2004b}.
In those two systems, replica symmetry breaking occurs concomitantly
with the onset of long range frustration.
When replica symmetry is broken and there are many (macroscopic) states
of global minimum energy, first, one needs more order parameters
to characterize the system in the non-frustrated phase; and second,
in the long--range frustrated phase,
the group of type-I unfrozen
variable nodes of one state as well as their
spin value correlations may be quite different from those of another
state. These two points make calculation quite difficult.
It is hoped that the present work will stimulate future efforts
on this line.

Second, the long--range frustrated mean field solution does
not evolve from the instability of the non-frustrated solution.
This is clear from the fact that, at $\alpha = \alpha_R(3)$,
the long range frustration order
parameter jumps to a positive value rather than gradually increases
from zero.
This is qualitatively different from what happens in the
random $2$-SAT and the vertex cover problem, where long range
frustration is caused by a propagation and percolation of
frustration.  Maybe the present frustrated solution correspond to
a metastable macroscopic state
rather than a state of global minimum energy.
We believe that long range frustration will also exist
in the ground--states of the random $3$-SAT problem when
$\alpha$ is larger than some threshold value. If this onset of
long range frustration is caused be a percolation of frustration
as assumed in this paper, the order parameter $R$ should gradually
increases from zero.

The author has also performed a stability
analysis of the replica symmetry breaking solution of
Ref.~\cite{MezardM2002b}, to investigate whether or not
long range frustration will occur gradually when $\alpha \geq 4.267$.
His preliminary simulation results indicate that this solution is
also locally stable at $\alpha \sim 4.267$.

                                %

                                %

\section{
  Conclusion and discussion
  \label{sec:4}
}

In a random $K$-SAT problem, some of the variable nodes are unfrozen,
their spin values change in different microscopic configurations
of global minimum energy.
However, these fluctuations of spin values among
different unfrozen variable nodes may be highly correlated.
In this paper, we have investigated the possibility
of such kind of correlations based on the physical picture of percolation
transition.
For the random $2$-SAT problem, we found that
long range frustration among unfrozen variable nodes gradually
builds up  as the clauses-to-variables ratio $\alpha$ exceeds
$\alpha_R(2) = 4.4588$. This value is larger than the SAT-UNSAT transition
point of $\alpha_c(2)=1$.
For the random $3$-SAT problem, we found a long--range
frustrated mean field solution when $\alpha > \alpha_R(3)=4.1897$.
The energy density of this solution increases gradually
from zero as a function of $\alpha$, while there is
a jump in the long range frustration order parameter $R$
at $\alpha_R(3)$.
The SAT-UNSAT transition point of this nontrivial solution
is lower than the value of $\alpha_c(3)=4.267$ as predicted by
the work of Refs.~\cite{MezardM2002,MezardM2002b,BraunsteinA2002}.
Two possible reasons for this discrepancy were mentioned.
This discrepancy indicates that, when replica symmetry breaking
occurs before the onset of long range frustration, the present
mean field theory needs to be improved. We hope the present
work will stimulate further efforts to overcome this difficulty.

The phase diagram of the finite connectivity $\pm J$
Viana--Bray spin glass model
was also discussed. We suggested the possibility of a phase transition
from a non-frustrated spin glass phase to a long--range frustrated
spin glass phase as a finite temperature. This prediction might be
checked by numerical simulations.

The method used in the present work may also be applicable
to other finite connectivity spin glass models \cite{VianaL1985}.
We hope that an appropriate combination
of long range frustration and the cavity method at the
first order replica symmetry breaking level \cite{MezardM2001,MezardM2003}
will help to advance our understanding of spin glass statistical
physics.

There exists a rigorously polynomial algorithm to solve the $2$-SAT
decision problem; but the $3$-SAT decision problem is NP-complete.
The proliferation of macroscopic domains in the solution spaces of the
$3$-SAT problem and its absence in the $2$-SAT problem is unlikely to
be the reason for this qualitative difference in computational
complexity, since there exist
class P (polynomial) combinatorial optimization problems
which also have exponentially many macroscopic states
in their solution spaces \cite{MezardM2003b,ZhouH2003d}.
In the author's opinion, an instance of a combinatorial
optimization problem may become intrinsically difficult if long range
frustration of the type discussed in this paper exists in
such a system.  Long range frustration causes strong correlations
among the fluctuations of the spin values of a finite fraction of
the vertices of the system. This means that, if the spin
on an unfrozen vertex is set to a given value, the spins on
other $O(N)$ unfrozen vertices should also be set to
the corresponding values. This spin value fixation process
may be extremely difficult to achieve even for a global
algorithm, since the algorithm needs to choose the
right vertices and the right spin values to fix.

In the random $2$-SAT problem, there is no long range frustration
at both sides of the SAT-UNSAT transition point. In the
vertex cover problem, there is an onset of long range
frustration in the computationally difficult case of
mean vertex degree $c \geq 2.7183$ \cite{ZhouH2004b}.
In the random $3$-SAT problem, we know there exists
a non-trivial solution with a jump of the long range
frustration order parameter $R$ at $\alpha_R(3)$.
Although $\alpha_R(3)$ is unlikely to be true SAT-UNSAT
phase transition point for this problem, we expect to
observe that, in a correct replica symmetry breaking
mean  field solution long range frustration will
builds up when the clauses-to-variables ratio
$\alpha \geq \alpha_c(3)$. To construct such
a mean field solution is still an open problem.

                                %

                                %

\section*{
  Acknowledgement
}

The author is grateful to Reinhard Lipowsky and Lu Yu for support and
discussion. He also thanks Jing Han and Ming Li for their general
interest.

                                %

                                %

redpajama_set_name: RedPajamaArXiv


Le Rostand has a truly wonderful view of the Jardins du Luxembourg from its classy interior, decked out with Oriental paintings, a long mahogany bar and wall-length mirrors. It's a terribly well-behaved place and you should definitely consider arriving in fur or designer sunglasses if you want to fit in with the regulars. The drinks list is lined with whiskies and cocktails, pricey but not as steep as the brasserie menu. Still, with a heated terrace in winter, it's perfect for a civilised drink after a quick spin round the gardens.


A database management system, DBMS, is similar to a set of spreadsheets that all interact together to keep company-wide data together in a secure location. With a DBMS companies can add data, manage it and access it later for statistical information that helps the company make changes and updates to policies and procedures. Without a DBMS companies would struggle to find accurate information about sales per customer, past due accounts receivable and much more that help customer service and revenue. DBMS's hold inventory, customer lists, vendors, accounting information that easily turns into reports and usable data. Relational DBMS's help limit data redundancy which would be strongly evident in a simple spreadsheet database format.
RDBMS's have keys that relate tables together, reduce data redundancy and make it much easier to run reports. For example, it's important to know that a sales person can have multiple customers and that customers only have one sales person. The primary key is a unique identifier that cannot be duplicated and, in this case, the Customer ID and Sales Person ID would both be primary keys. Therefore, two customers cannot both have the same number, the system will block it from happening. Candidate keys often happen in the customer and inventory sections of a DBMS, because it's difficult to remember that a customer's ID is "1234." Instead a second identifier, or candidate key, would be the name of the customer or the description of the inventory item so that it can be searched instead of memorized.
Secondary keys are used mostly in reporting. A secondary key example would be a city, state or zip code as they do not have to be unique. Instead, they are something common that will help run reports by zip code, by sales person name or by a certain type of inventory. Foreign keys get more complicated in a RDBMS because they are primary keys from different tables. A customer table will often display orders, so the primary key of the orders table would end up being the foreign key of the customers table. The customers table may have a second foreign key of Sales Person ID to see who entered the order. Finally, a combination key is somewhat rare, but it occurs when the table lacks a primary key. Instead a combination of two keys act as a combination key such as a student that's registered in three classes. The Student ID and Course ID would act as a combination key.
Entity relationship diagrams are a visual of everything explained above. The diagram shows each table in the system and how each table interacts with the other tables. For instance, one sales person with multiple customers would be shown in the diagram as a one-to-many relationship with a (1----M) connection between the tables. The line shows the relationship between the tables so that the user interface (UI) can display both items together. It's often that a sales person is viewing all of their customers so they need to be related in the DBMS. An associative entity occurs in the middle of a many-to-many (M:N) relationship such as inventory and orders. In this scenario a third table is created between the two such as Order Line for correct cardinality.


text:
Q: bidirectional_rnn: inputs must be a sequence I want to try the bidirectional_rnn to predict time series. code is :
   #BiRNN_model.py
import tensorflow as tf

class BiRNN(object):
"""
a bidirection RNN
"""

def __init__(self, in_size, out_size, num_steps=20, cell_size=20, batch_size=50,
             num_layers=2, keep_prob=0.5, is_training=True):
    """
    :param in_size: int, the dimension of input
    :param out_size: int, the dimension of output
    :param num_steps: int, the number of time steps
    :param cell_size: int, the size of lstm cell
    :param batch_size: int, the size of mini bacth
    :param num_layers: int, the number of  cells
    :param keep_prob: float, the keep probability of dropout layer
    :param is_training: bool, set True for training model, but False for test model
    """
    self.in_size = in_size
    self.out_size = out_size
    self.num_steps = num_steps
    self.cell_size = cell_size
    self.batch_size = batch_size
    self.num_layers = num_layers
    self.keep_prob = keep_prob
    self.is_training = is_training
    self.__build_model__()

def __build_model__(self):
    """
    The inner method to construct the BiRNN model.
    """
    # Input and output placeholders
    self.x = tf.placeholder(tf.float32, shape=[None, self.num_steps, self.in_size])
    self.y = tf.placeholder(tf.float32, shape=[None, self.num_steps, self.out_size])

    # Add the first input layer
    with tf.variable_scope("input"):
        # Reshape x to 2-D tensor
        inputs = tf.reshape(self.x, shape=[-1, self.in_size])  # [batch_size*num_steps, in_size]
        W, b = self._get_weight_bias(self.in_size, self.cell_size)
        inputs = tf.nn.xw_plus_b(inputs, W, b, name="input_xW_plus_b")
        # inputs = tf.matmul(inputs,W)+b
    # Reshep to 3-D tensor
    #inputs = tf.reshape(inputs, shape=[-1, self.num_steps, self.cell_size])  # [batch_size, num_steps, in_size]
    inputs = tf.reshape(inputs, shape=[-1,  self.in_size])

    # Dropout the inputs
    if self.is_training and self.keep_prob < 1.0:
        inputs = tf.nn.dropout(inputs, keep_prob=self.keep_prob)

    #Construct birnn cells
    biRNN_fw_cell = tf.contrib.rnn.BasicRNNCell(num_units = self.cell_size)
    biRNN_bw_cell = tf.contrib.rnn.BasicRNNCell(num_units = self.cell_size)
    if self.is_training and self.keep_prob < 1.0:
        fw_cell = tf.contrib.rnn.DropoutWrapper(biRNN_fw_cell, output_keep_prob=self.keep_prob)
        bw_cell = tf.contrib.rnn.DropoutWrapper(biRNN_fw_cell, output_keep_prob=self.keep_prob)
    cell_Fw = tf.contrib.rnn.MultiRNNCell([fw_cell] * self.num_layers)
    cell_Bw = tf.contrib.rnn.MultiRNNCell([bw_cell] * self.num_layers)

    #the initial state
    self.init_state_fw = cell_Fw.zero_state(self.batch_size, dtype=tf.float32)
    self.init_state_bw = cell_Bw.zero_state(self.batch_size, dtype=tf.float32)

    #add biRNN layer
    with tf.variable_scope("BRNN"):
        outputs,final_state_fw,final_state_bw = tf.contrib.rnn.static_bidirectional_rnn(cell_Fw,cell_Bw,inputs,
                                                                                initial_state_fw =self.init_state_fw,
                                                                                initial_state_bw = self.init_state_bw
                                                                                )
    self.final_state_fw = final_state_fw
    self.final_state_bw = final_state_bw

    # Add the output layer
    with tf.variable_scope("output"):
        output = tf.reshape(outputs, shape=[-1, self.cell_size])
        W, b = self._get_weight_bias(self.cell_size, self.out_size)
        output = tf.nn.xw_plus_b(output, W, b, name="output")

    self.pred = output
    losses = tf.contrib.legacy_seq2seq.sequence_loss_by_example([tf.reshape(self.pred, [-1, ])],
                                                                [tf.reshape(self.y, [-1, ])],
                                                                [tf.ones([self.batch_size * self.num_steps])],
                                                                average_across_timesteps=True,
                                                                softmax_loss_function=self._ms_cost)
    self.cost = tf.reduce_sum(losses) / tf.to_float(self.batch_size)

def _ms_cost(self, y_pred, y_target):
    """The quadratic cost function"""
    return 0.5 * tf.square(y_pred - y_target)

def _get_weight_bias(self, in_size, out_size):
    """
    Create weight and bias variables
    """
    weights = tf.get_variable("weight", shape=[in_size, out_size],
                              initializer=tf.random_normal_initializer(mean=0.0, stddev=1.0))
    biases = tf.get_variable("bias", shape=[out_size, ], initializer=tf.constant_initializer(0.1))
    return weights, biases

but, if i run the code ,this is a error that:
  File "../model/BiRNN_model.py", line 70, in build_model
    initial_state_bw = self.init_state_bw
  File "/home/lucas/.local/lib/python3.5/site-packages/tensorflow/contrib/rnn/python/ops/core_rnn.py", line 328, in static_bidirectional_rnn
    raise TypeError("inputs must be a sequence")
TypeError: inputs must be a sequence
the inputs parameter in static_bidirectional_rnn is not a sequence. I'm new for tensorflow and Deep Learning, I have spent many days to try to fix this error, but i failed. Can someone to help me? thx.

A: I'm assuming that you want to create a fully unrolled bidirectional recurrent neural network as this function 'static_bidirectional_rnn' is used. The function expects a sequence of tensors, so the input should be unpacked ('unstack' in recent tf versions) in the time-steps direction.
The error is in this line, as it does not contain time steps:
inputs = tf.reshape(inputs, shape=[-1,  self.in_size])

it should be something similar to the following:
inputs = tf.unstack(inputs, self.num_steps, 1) # Unstack to get a list of 'self.num_steps' tensors of shape (batch_size, in_size)

redpajama_set_name: RedPajamaStackExchange


Published 04/25/2019 06:25:03 am at 04/25/2019 06:25:03 am in 12 Wide Garage Door.
12 wide garage door wide garage doors 12 foot wide garage door for sale garage door foot wide garage door r on simple regarding full size of garage doorthe super favorite foot wide garage door picture.
wide garage doors squadrco wide garage doors foot wide garage door for sale, garage doors vinyl garage doors, garage doors courtyard collection steel garage door, wayne dalton garage door bottom weather seal genuine part number wayne dalton garage door bottom weather seal genuine part number wide doors, purchase neurontin mg tablets online cheap shop for neurontin purchase neurontin mg tablets online cheap shop for neurontin mg tablets with credit card neurontin mg tab accept mastercard, x garage door goldenfeedinfo x garage door ft x ft garage door central for foot wide garage, photo gallery of garage door styles in pittsburgh western pa area get , car wide extra deep garage plans x x , xtreme garage door threshold wide kit garage door xtreme weather guard wide xl overhead door threshold kit, wide garage doors tall garage doors high marvellous ft door wide garage doors tall garage doors high marvellous ft door decor foot wide, fully enclosed metal buildings metal carport depot please be aware with newly announced tariffs on steel all prices are subject to change by the manufacturer without notice at any time.


text:
Favorite and Featured Brands:
Patek Phlippe
There is more:
View Full List of Timepiece Makers and Luxury Brands »
Behind The Scenes: Independent Watch Brand Armin Strom's Watchmaking Facilities (Video)
Earlier this week, we spoke to our good friends and colleagues over at TheWatchesTV, who gave us permission to use a few of their wonderful videos here on our site. While we won't do this often, we can't help but get excited about a walk through a Manufacture captured on video. Recently, when MAD visited…
1 year ago in Brands, Educational info, Interviews, News Videos/Slide Shows, Timepieces News, Reviews and Articles
Does Anyone Have A Score Card For The Revolving Doors Of The Swiss Watch Industry?
Well, I am not going to sugar coat this. The Richemont Group is making some more changes in the ranks, and one or two of them are quite interesting. Alain Zimmermann, long-time CEO of Baume & Mercier will be stepping aside in June as he heads into a newly created Richemont Corporate position as head…
1 year ago in Affordable Watches, Brands, Jaeger-LeCoultre, News, News Videos/Slide Shows, Panerai, Timepieces News, Reviews and Articles
Introducing An American Special: The A. Lange & Sohne Saxonia Annual Calendar U.S. Boutique Edition (Price)
Easily one of the best-selling timepieces for German watch brand A. Lange & Sohne is the incredibly beautiful Saxonia Annual Calendar watch. Since it was first introduced to the world eight years ago in 2010, this model has been a benchmark in the realm of calendar watches thanks predominantly to its oversized date feature. Now,…
1 year ago in A. Lange & Sohne, Brands, Reviews and Articles, Timepieces News, Reviews and Articles, Women's watches
Introducing The New $108,000 MB&F HM7 Aquapod Green/Titanium Watch, Inspired By JellyFish (Price)
Today, we are happy to introduce MB&F fans to the newest HM7 Aquapod watch — clad in green and looking mean. Indeed, after the two launch editions last year– one in 18-karat 5N rose gold with a black bezel and the beloved titanium version with a blue bezel — MB&F now unveils a second titanium…
1 year ago in Basel World 2018, Brands, MB&F, Timepieces News, Reviews and Articles, Women's watches
Carl F. Bucherer Unveils Baselworld 2018 New Watches, Including Manero Double Peripheral Tourbillon: Video
Following the Baselworld 2018 exhibition, there is so much to cover — we literally saw nearly 100 brands and several thousand watches, that it takes a little time to get close-up with each brand. While we are putting together our hands-on reviews, though, we tap into the great video done by our friends at TheWatchesTV.…
1 year ago in Affordable Watches, Basel World 2018, Brands, Carl F. Bucherer, Interviews, Timepieces News, Reviews and Articles, Watch Shows 2018, Women's watches
Greubel Forsey and Franco Cologni Awarded by FHH Cultural Council
On April 18 at Cite du Temps in Geneva, the Fondation de la Haute Horlogerie's Cultural Council announced the winners of this year's awards that honor exceptional personalities and professionals who have left a significant stamp on the watch world vial creative, artistic and technical mastery. During the 6th annual "Hommage au Talent" award ceremony,…
1 year ago in Brands, News, Timepieces News, Reviews and Articles, Watch Shows 2018
4748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271

redpajama_set_name: RedPajamaCommonCrawl


This post is from monthly contributor, Cheryl.
Savvy brands know the value of online word-of-mouth endorsements. Whether they're called reviews, product placements or sponsored posts, endorsements from influential bloggers have proven to be key in product sales and awareness. So, what's a brand to do if they struggle when connecting with independent bloggers to endorse their products? Below are 5 potential reasons bloggers are NOT working with your brand.
Are you guilty of these offenses?
You've probably heard it said social media is a conversation. Bloggers are in the business of relationships; it's what makes blogger endorsements valuable. Just as they have relationships with their readers, bloggers want to form relationships with you, the brand. Before you pitch a blogger, take a few moments to get to know them via their blog. Read their about page, explore their post categories, read conversations in the comments. And please, please, make sure you have their name and blog spelled correctly. Starting a pitch letter with "Dear Blogger" practically guarantees your pitch will be deleted.
Generally, bloggers are a loyal breed. While you're exploring the potential site, take note of brands they've worked with previously. Have they reviewed similar products? Is there an abundance of posts for a specific brand? Do they hold ad space for that brand as well? If so, they may be already committed. This doesn't mean you can't pitch them! Just be aware, acknowledge the elephant in the room, and respectfully plead your case about why you feel your product would be a great fit too.
This is one of the most common educational-brand mistakes. Being approachable equates to engagement. Be sure to give ample room to engage (i.e. have conversations with) your audience. Do more than share the latest updates about your brand! That's called broadcasting, and again, social media is a conversation. Ask questions, share relevant updates of your followers, comment (genuine comments, not spam). A little engagement goes a long way to demonstrate your approachability as a brand.
Yes, there are bloggers who will do product-placement posts for product only, especially if they really desire your product. However, in general, if you want a blogger with a larger, focused following, expect to pay. In the homeschool blogger arena, fees vary greatly from $25 to $150 or more (good news: many bloggers are negotiable). Why do bloggers charge? Because they should be compensated for their time, creativity, reach, and taxes they're obligated to pay for accepting products. Period.
Sometimes, it's just a matter of timing. For most, blogging is a part time job. For everyone, there are a limited number of hours a day to devote to blogging. If a blogger is in high demand, their editorial calendar will fill up quickly. In which case, it's not that they don't want to work with you, it's that they can't. Wait 6 months and try again (unless you've been given a concise "no"). Remember, having a successful campaign which includes product-placement posts, goes beyond sending en masse pitches. It takes thought, tact, and engagement. Creating a working relationship with a blogger whose readership responds to your products is worth the investment.
Cheryl Pitt is a brand consultant and founder of the 2:1 Conference – a social media event for bloggers who homeschool and the brands they love. Cheryl blogs at cherylpitt.com.
this is such a GREAT post! So often we're given more things they have to should do need to do as bloggers — but a lot of the time brands are not on the same page!
Great article! Now if I could just get some friends with businesses to read this! Reposting! Thanks Cheryl!


text:
2019 Buncombe Summit Hill Climb 5k set
Normandy trip success, but not without lots of work
Details come to light about death at falls
Band of BlackHawks at Normandy
Yearout out a year early
Yard sale draws 'insane' crowds
Girls Scout troop making a difference
Yoga business offers "curated" classes
The public's right to know
Town withholding info from public
Home/News/What You Don't Know About Historic Swearing-In
What You Don't Know About Historic Swearing-In
Complete Details Of New Chain Of Command Structure At The Sheriff's Office
Facebook Twitter Google+ LinkedIn StumbleUpon Tumblr Pinterest Reddit VKontakte Odnoklassniki Pocket WhatsApp
Quentin Miller is sworn in as sheriff of Buncombe County.
Editor's Note this story was updated at 1:25 pm on Thursday, Dec. 6, 2018
By Chad Nesbitt
Asheville – Monday December 3rd was a historical day in Buncombe County as Quentin Miller (D) was sworn in as the first African American Sheriff of the county. Hundreds gathered at the Buncombe County Court House for the swearing-in ceremony. Those in attendance were friends and family of Sheriff Miller, leaders of the Democrat Party, judges, and law enforcement officers.
Chief District Judge Calvin Hill presided over the ceremony. Former chairman of the Buncombe County Democrat Party Bruce Peterson introduced Sheriff Miller and his wife Karen.
Once sworn in Miller said, "I want to thank my Lord and Savior Jesus Christ." Miller said, "I look forward to doing what we talked about and that is being a community of "We." Miller then said, "We know this is about De-escalation. This is going to be a learning curve. We all have to come to the table and be honest and transparent."
"It's not my office. It's our office and help us transition into 21st Century policing," Miller said. "I'm in a good place. The Sheriff's office is left in a really good place and that's because of Van Duncan." Former Sheriff Van Duncan did not attend the ceremony. Duncan said, "I had a previous scheduled meeting with friends."
Officers the Leader spoke with said Miller was late swearing in as Sheriff. One deputy that wanted to remain anonymous said, "Sheriff Duncan made Randy Smart interim Sheriff until Sheriff Miller could be sworn in." Sheriff Van Duncan confirmed that Smart was made interim until Miller took over. Duncan said, "The state told me my last day was November 30th so I put Randy Smart in charge until Quentin could be sworn in."
According to NC General Statutes sheriffs newly elected in November are scheduled by law to take office on the first Monday in December after the election. This pursuant to N.C. Gen. Statute 163-1.
Buncombe County Board of Elections Director Trena Parker said, "The law just says a new sheriff is to take office on the first Monday in December. It doesn't give a specific time."
Tennessee Attorney John Lauter said, "A new sheriff really needs to be sworn in at 12 am because his job demands it. You never know when a deputy may get shot or catastrophic thing might happen." Lauter said, "Just imagine someone started shooting people at a concert and Quinten started making decisions, directing officers without legally being sworn in. A good defense lawyer would have fun with that. For legality reasons the newly-elected sheriff needs to go in at 12 am."
Duncan told the Leader, "Even though the state said I had to retire November 30th if something catastrophic happened I would be there until Quentin was sworn in."
WHAT WAS SAID/NOT SAID AT THE CEREMONY
Sheriff Miller did not say how the de-escalation of a police force was going to stop Buncombe's opioid problem or school safety except to say de-escalation was going to be a "learning curve".
Buncombe County resident Marissa Martin attended the ceremony. Martin said, "I am a black woman who voted for Shad Higgins but Miller is now sheriff and I stand behind him."
Asked why she didn't vote for Quentin Miller? Martin said, "I am concerned for the safety of these officers and our community. He, (Miller), supports handing these needles out like that place in West Asheville where I live. To me this just tells more drug dealers to come to my neighborhood. How's that gonna stop drugs in our communities and our schools?" Martin said, "I am a Christian woman and I am trusting that Mr Miller will do the right thing."
WHO IS IN CHARGE?
According to the command structure charts sent out to officers, Sheriff Miller's right hand man is Chief Deputy Don Eberhartd and comes highly recommended from all local law enforcement communities. In a Facebook post Eberhartd said, "I became an officer because I see the profession as a ministry, a ministry to be a blessing to others." Eberhartd said, "The real task in today's law enforcement profession is leaving the person in a better situation after the encounter than they were before the encounter."
Miller has chosen Darryl Fisher to run the Buncombe County Jail and security at the courthouse. Fisher made some controversial statements that went national while he was running for sheriff in the Buncombe County Democrat primary. In a video from a Mom's Demand Action meeting in early March 2018 Fisher says, "You've heard people say, "You'll have to pry my guns from my cold dead hands. Well…OK." In an exclusive interview with the Leader, Fisher said he just meant that "all in good humor." (see pictures below for complete detail of chain of command structure)
MILLER'S LETTER TO OFFICERS
An anonymous source has provided the Leader a letter from Miller to all Buncombe County Sheriff Department employees. It includes a list of the chain of command. It is as follows:
"The Community of WE Here at the Buncombe County Sheriff's Office
Today, I am humbled and honored to be sworn in as the next Sheriff of Buncombe County. I look forward to working with you, and continuing to provide the excellent service to the residents of Buncombe County that has been a hallmark of the Sheriff's Office.
As with any new administration, there will be some organizational changes. Attached you will find new organizational charts for our Sheriff's Office. Please be advised that if you have not had a one-on-one conversation with myself, or another member of Command Staff regarding a change of assignment, you are safe to assume that you will continue in your present duties as assigned, at your current pay rate.
Again, I look forward working with all of you, as well as getting to know all of you. This is a large agency, and we serve a large community—there will be a learning curve for us working together as a team, but I am committed to making sure that we continue to excel in our work to serve the residents of Buncombe County as we build "The Community of WE".
Your sheriff,
Quentin Miller"
Editor's Note: For those would go as far as to look-up Mrs. Martin's registration it is not listed under that name. While she goes by "Marissa" that is not the name she is registered under with the Buncombe County Board of Elections. I can tell you I understand that because at the Board of Elections in Madison County they have me as Charles, but I go by "Clint."
New Buncombe County Sheriff's Office Chain of Command Charts
Buncombe County Sheriff Buncombe Sheriff Chain Of Command Structure At Buncombe Sheriff's Office Historic sheriff Quentin Miller Quentin Miller is sworn in as sheriff of Buncombe County Van Duncan
Weaverville Tribune
Covering North Buncombe County.
Proposed I-26 Connector Public Hearing Today
North Carolina Ranks No. 11 In Opioid Sales
Truck Collides With Bridge, Spills Fuel, Shuts Down Interstate For Hours
Man dies at Reems Creek Falls
Home where man was murdered destroyed by fire
Weaverville, NC
2019 Buncombe County Tax Notices
Bridge Fall Stranding Eight Fire Vehicles
Mother Says Attempted Abduction Of Daughter Happened Again
An early morning fire destroys local business
Buncombe DA's Dismissal Of DWI Case Draws Ire Of MADD Leader
Construction Accident Closes Reems Creek Road for MAMA
Why do people who try and protect their little fiefdom alway...
Sounds like it might be a story...Who is this player?...
It's interesting how the first ever NB football player to ge...
thanks will pass it along to the Dry Ridge Museum...
weavervilleman
Its the weaver house off of monticello! I cant believe you g...
The Tri-Cities TN


text:
Hi-Tech / Hardware
Network and communications
Apple has already placed orders. iPhone 2020 expects a boost in performance thanks to a new SoC
IXBT.com fresh news all the sections together 22.02.2019 at 16:16
IXBT.com (http://www.ixbt.com) — specialized Russian information-analytical server, covering the hardware of personal computers, communications and servers, 3D graphics and audio, digital photo and video, Hi-Fi equipment and projectors, mobile phones and peripherals, gaming applications and more.
Taiwanese manufacturer Taiwan Semiconductor Manufacturing (TSMC) has reserved orders on the first 5-nanometer system on a chip from Apple. This was reported by the resource DigiTimes, citing industry sources.
According to the source, a new SoC designed for the iPhone, scheduled for release in 2020. Earlier it was expected that TSMC will go into production according to the norms of 5 nm in the first half of 2019, and mass production is 5-nm production will start in the second half of 2019. As reported now, mass production in the hard ultraviolet range (EUV) at rates of 5 nm will begin in 2020.
For the last three years, TSMC remains the exclusive provider of branded Apple SoC, starting with 16-nm Fusion A10 in the iPhone 7/7 Plus, and then 10-nm A11 Bionic to iPhone and iPhone Plus 8/8 X 7-nm A12 Bionic to iPhone XR/XS/XS Max. This year it is expected A13 7-nanometer technology, but it will be the first with the technology of lithography in the hard ultraviolet range.
End users can expect from this transition is significantly raised productivity and reduced energy consumption.
Read more on site ixbt.com
New electric scooter Xiaomi has a power reserve of 45 km 16.02.2019 at 17:53
Google will teach pre-installed on the smartphone app to be updated without having to log in to your account, the search giant 16.02.2019 at 17:03
Apple bought a startup DataTiger to "rethink the whole marketing experience" 16.02.2019 at 16:56
Attack of the clones: the Samsung Galaxy A50 will be similar to the budget Galaxy M 16.02.2019 at 16:31
At Vivo too, will be a technology super-fast charging for smartphones 16.02.2019 at 16:18
Samsung no longer releases Blu-ray players 16.02.2019 at 16:17
Not impressed: mobile GeForce RTX 2070 ahead of mobile GTX 1070 only 10% 16.02.2019 at 11:01
Don't expect smartphones Huawei P30 and P30 Pro high-resolution displays 16.02.2019 at 10:02
In the spring Apple will release an updated AirPods headphones in black color and with a matte finish 16.02.2019 at 09:55
The production of chips Apple Lightning to A13 of the new iPhone will begin soon 11.02.2019 at 11:32


text:
Terrorists Can't Kill Charlie Hebdo's Ideas
Jordan Golson
With continuous live blogs and hands-on reports of wearables and televisions streaming out of Las Vegas, we must stop and consider the horror of what has happened in Paris.
People in Nice, in southeastern France, hold posters reading 'I am Charlie' as they gather to express solidarity with those killed in an attack at the Paris offices of weekly newspaper Charlie Hebdo, on the evening of Wednesday, Jan. 7, 2015.Lionel Cironneau/AP
"A man may die, nations may rise and fall, but an idea lives on. Ideas have endurance without death."—JFK
I don't want to talk about technology or cars for a minute.
I promise to get back to talking about the Challenger Hellcat, and whatever awesomely ludicrous thing Elon Musk comes up with next, soon.
But with continuous live blogs and hands-on reports of wearables and televisions streaming out of Las Vegas, we must stop and consider the horror of what has happened in Paris. A barbaric and unforgivable act, committed by uncivilized thugs hellbent on stifling any dissent and criticism they deem unworthy.
[#contributor: /contributors/59094a34d8c8646f38eef2c0]|||Jordan Golson is a technology and automotive reporter based in Durango, Colorado.|||
Masked men armed with rifles stormed the headquarters of the satirical magazine Charlie Hebdo in the heart of Paris and killed 12 people. The dead included four political cartoonists, editor in chief Stéphane "Charb" Charbonnier and two police officers.
The three gunmen fled after a firefight with police, and are reported to have now been identified. One of the slain officers had been named Charbonnier's bodyguard after he received numerous death threats from Islamic extremists.
The attack appears to have been in response to the magazine's frequent publication of cartoons mocking the Islamic prophet Muhammad. One gunman reportedly shouted, "We have avenged the prophet Muhammad, we have killed Charlie Hebdo" as he jumped into a getaway car.
Although the shooting occurred at Charlie Hebdo, it was an attack on all journalists. More than that, though, it was an attack on all of us, because it was a direct offensive on a way of life, on freedom of speech, and on the storied tradition of speaking truth to power.
https://twitter.com/davpope/status/552844593046097920
Journalism is, almost by definition, sharing information that might offend or cause discomfort to someone. As Finley Peter Dunne famously said, the job of a journalist is to comfort the afflicted and afflict the comfortable. Journalists are hardly alone in this; writers, artists and musicians have long courted controversy, especially when commenting on religion. Iran called for the assassination of author Salman Rushdie following the publication of his book The Satanic Verses, while artist Andres Serrano enraged many with his anti-Christian piece Piss Christ.
Whether it's an interview with a CIA whistleblower who alerts us to widespread government surveillance who some consider a traitor, or reporting the details about an upcoming Apple product launch, it's difficult to write anything of consequence that won't upset someone (as most comment sections on the Internet show).
Satire is a particularly pointed form of social commentary, used for thousands of years to illustrate the hypocrisy, greed, and absurdity of the powerful. It isn't all as elegant as that written by Aesop and Miguel de Cervantes, or even Stephen Colbert. Some is awkward and clumsy, and some of it is flat-out bad. You can argue, and many have, that the cartoons printed in Charlie Hebdo fall into this category. That is beside the point. Satire is an essential tool for revealing hard truths about our world. It must be protected in all its forms.
A man holds up an edition of Charlie Hebdo magazine as people gather on the Place Royale in Nantes, western France, on January 7, 2015, to show their solidarity with the victims of the attack on the offices of the satirical weekly in Paris. Muhammad's speech bubble in the cartoon reads, in French, "A hundred lashes if you don't die laughing."
Georges Gobet/AFP/Getty Images
Another bit of satire has been in the news recently, that of the North Korea-mocking movie The Interview. The film, a buddy comedy about two "journalists" hired by the CIA to kill North Korean dictator Kim Jong-un, so enraged North Korea that—if you believe the U.S. government—it aimed an army of hackers at Sony Pictures Entertainment and stole sensitive data to embarrass Sony and force the company to withdraw the film.
It worked, sort of: several theater chains declined to show the film amid security fears. After much back and forth, Sony released the film online and in a small number of theaters. It has since become Sony's highest grossing video on demand release.
The stereotyping verges on outright racism throughout the film and, in the long run, The Interview will likely be more meaningful for the future of movie distribution than as effective political satire. But, improbably, many more people are now familiar with North Korea's disappointing record on human rights and its inability to feed itself than before the film was released.
The attack on Charlie Hebdo is ultimately about control. Masked cowards wanting to decide what we can and can't see. Wishing to tell us what to believe in and what to hold dear.
This is nothing new, of course. There have always been radicals looking to force their view of the world on others. But this struck me dumb. Maybe it's because I'm a writer, and the slain were writers. Authors and artists and other so-called intellectuals have always been the first to stand in the public square and call out evildoers, knowing the price they could pay for these necessary actions. Charbonnier and his staffers paid that price today. We all did.
The attack on Charlie Hebdo is ultimately about control. Masked cowards wanting to decide what we can and can't see.
The goal of terrorism is to make us feel helpless and scared, to cower in the face of threats. To make us choose to live our lives in a way other than how we wish. To question our very existence.
When I heard the news of the massacre, I questioned mine. But probably not in the way that the terrorists wanted.
Nothing I have ever written has angered someone to the point of violence. I hope it never does. At times like this, I wonder what impact my writing—about cars and Apple, mostly—really has on the world. Or that of my colleagues, spending time in the desert to bring you the latest on über-thin televisions and self-driving cars. But personal expression—whether it's a movie, a speech, a painting or a blog post—is given value by its reader. We write to be read. We write to have an impact on the world. Sharing hands-on impressions of the latest smart wristband may not change the world, but it has value. It matters in its way.
Today, all journalists have been attacked. Our colleagues in Paris have been brutally murdered for something they created with pen and ink (or their digital equivalents). Something they created that was simultaneously harmless and harmful, inane and enraging.
And with their tragic and indefensible deaths, we have been enraged. The cartoons in Charlie Hebdo may have been graceless and intentionally provocative and not funny. Tech journalism may sometimes be unimportant and vapid and self-indulgent. But all speech plays a part in creating a civilized society, whether from Demosthenes and Bill O'Reilly, Marshall McLuhan and Lawrence Lessig, or TechCrunch and Gizmodo.
As Charbonnier said two years ago, "I'd rather die standing than live on my knees." We all have an obligation to stand with him, to tell truth to power, and to forever ensure that our fellow journalists did not die in vain.
May the ideas live on. Je suis Charlie.
Jordan Golson is a technology and automotive reporter based in Durango, Colorado. Email: jlgolson@gmail.com Twitter: @jlgolson


When home skin care products aren't effective, but you aren't ready for surgery, consider nonsurgical skin rejuvenation treatments, like Microneedling. Plastic surgeon Dr. Richard Bensimon is pleased to offer Microneedling (also known as collagen induction therapy) at his office in Portland, OR. Microneedling uses many fine-gauge needles to safely and effectively create micro-injuries in the needed areas of the skin. The micro-injuries trigger the body's natural production of collagen and elastin, two nutrients that contribute to the health and appearance of your skin. Easily combined with other skin treatments, like vitamin-rich serums, Microneedling can help reduce scars, stretch marks, and pores. Schedule a consultation at Bensimon Center to learn more about the benefits of Microneedling and ways to customize the treatment for your skin needs and goals.
"I feel really comfortable and happy I found Bensimon Center I had a few procedures done there, the result for my Botox was wonderful. The second was MicroNeedling I just did my first treatment today, I know the results are going to be great. AMBER is the BEST! she makes me feel so comfortable and safe! when I walk in their center. My acne scars have always been something that bothered me! now thanx to Bensimon Center I don't have to worry about them no more. Can't wait for the results to start showing!"
You may benefit from microneedling if you have slight to moderate skin issues, like rough skin texture, acne scarring or low elasticity. Microneedling treatments can also reduce the appearance of pores, stretch marks, and scars. You should be willing to wait a while before seeing the results of your Microneedling treatment since the collagen and elastin will need time to have an effect on the skin, but you will have natural-looking results and gain better overall skin health.
Microneedling is performed in a treatment room in about 30 – 60 minutes with numbing cream, but most patients feel mild or no discomfort. The skin will be cleansed before the Microneedling handpiece is passed evenly over the target area. After the Microneedling is performed, a topical treatment, such as a vitamin-infused serum, can be applied for deeper penetration of the nutrients into the skin. A sunscreen will be applied as your skin will be sensitive to sunlight after the treatment.
The cost for microneedling will vary, depending on what is included in your treatment plan. During your initial consultation, Dr. Bensimon and his Master Aesthetician will perform a skin analysis and then develop your unique treatment plan. From there, he will be able to explain your costs and what to expect during the procedure. Bensimon Center often offers specials on skin treatment packages so be sure to ask about current deals during your consultation.
During the Microneedling process, channels are created in your skin that make it easier for treatments to penetrate the deeper layers. This is why Microneedling is often combined with other treatments, like vitamin-rich serums or platelet-rich plasma (PRP). Microneedling with PRP has become known as the vampire facial. During your consultation, Dr. Bensimon and his Master Aesthetician can discuss what treatments may be performed along with Microneedling and which would most benefit your skin.
Most patients get 3 – 6 Microneedling sessions to achieve their best results. However, the number of treatments you need will depend on the condition of your skin and your goals. Microneedling can be safely performed every 4 – 6 weeks as needed. During your consultation, Dr. Bensimon and his Master Aestehtician will be able to estimate how many treatments you will need based on your skin and goals. Once you have reached your goal, Dr. Bensimon recommends getting maintenance treatments every six months.
Improve the health and appearance of your skin with microneedling therapy at The Bensimon Center in Portland, OR. A minimally invasive treatment that can give you dramatic results, microneedling boosts your natural production of collagen for smoother, firmer skin. Schedule a consultation with plastic surgeon Dr. Richard Bensimon and his Master Aesthetician to learn more about this procedure and other skin rejuvenation procedures.


text:
This is a list of gliders/sailplanes of the world, (this reference lists all gliders with references, where available)
Note: Any aircraft can glide for a short time, but gliders are designed to glide for longer.

W

W.W.S.
(Wojskowe Warsztaty Szybowcowe – military glider workshops)
 W.W.S.1 Salamandra
 W.W.S.2 Żaba (Frog)
 W.W.S.3 Delfin (Dolphin)

Waco
 Waco CG-3A
 Waco CG-4A
 Waco CG-13A
 Waco CG-15
 Waco Primary
 Northwestern PG-1 (CG-4)
 Ridgefield PG-2 (CG-4)
 Waco PG-3 (CG-15)
 Waco LRW (CG-4)
 Waco LR2W USN transport glider

Wagener
(H. Wagener)
 Wagener H.F.V. 17 Pirat

Waibel-Butler
(Gerhard Waibel & Dick Butler & Loek Boermans & Johannes Dillinger)
 Waibel-Butler Concordia

Walker
(Sam Walker)
 Walker Aria

Wallisa
(Józef Walis)
 Wallisa S-I (Willis S.1 or Walis S-1)  No.18 – Second Polish Glider Contest 17 May – 15 June 1925
 Wallisa S-III No.19 – Second Polish Glider Contest 17 May – 15 June 1925

Walters
(Fred Walters)
 Walters Sinbad I

Walther
(Don Walther of Christchurch, New Zealand )
 Walther Boffin-Coffin

Warczewski
(J. Warczewski – No.16 – Second Polish Glider Contest 17 May – 15 June 1925)
 Mechanik (glider) (Mechanic)

Warner
(Martin Warner & Allan J. Campbell)
 Warner Brolga
 Warner Kite 2
 Warner-Campbell Kite 1

Warszawa Uczniów Gymnazjum
(Chrzanowski-Gymnasiums in Warszawa)
 Warszawa Uczniów Gymnazjum glider

Wassmer
(Ets. Benjamin Wassmer / Wassmer Aviation SA)
 Wassmer WA 20 Javelot
 Wassmer WA 21 Javelot II
 Wassmer WA 22 Super Javelot
 Wassmer WA 22 Super Javelot 64
 Wassmer WA-22-28
 Wassmer WA-23
 Wassmer WA 26 Squale
 Wassmer WA 26 CM Squale Marfa
 Wassmer WA 28 Espadon
 Wassmer WA 30 Bijave
 Wassmer KBK-10
 Wassmer-SIREN H-230

Watson-Northrop
(J.P. Watson & Jack Northrop)
 Watson-Northrop 1929 glider

Weber
(Ernst Weber)
 Weber EW-1 – ANDRÖS, & MÜLLER
 Weber EW-2
 Weber EW-3 Libelle
 Weber EW-18
 Weber 108-16 RLM designation for EW-2

Weber
(Günther Weber - East Germany [DDR - Deutsches Demokratische Republik])
 Weber We-3 1971
 Weber We-4 1964

Weber-Landholf-Münch
 Weber-Landholf-Münch WLM-1
 Weber-Landholf-Münch WLM-2

Weiss
(José Weiss)
 Weiss 1914 glider
 Weiss Joker
 Weiss Olive

Weltensegler
(Weltensegler G.m.b.H)
 Weltensegler Feldberg aka Strandpromenade ?)
 Weltensegler Baden-Baden Stolz

Wenham
 Wenham Multiplane 1858

Westmacott
(R. J. Westmacott & K. Westmacott)
 Westmacott Skylark

Wezel
(Martin Wezel Flugzeugtechnik)
 Wezel Viva
 Wezel Apis 2

Whigham
(Eugene Whigham)
 Whigham GW-1
 Whigham GW-2
 Whigham GW-3
 Whigham GW-4
 Whigham GW-5
 Whigham GW-6
 Whigham GW-7

Whisper
(Whisper Aircraft)
 Whisper Motor Glider

Whitehead
(Gustave Whitehead, née Weiskopf)
 Whitehead 1897 glider

Widmaier
(Kuno Widmaier / IPE - Industria Paranaense de Estruturas)
 Widmaier GB-1 Quero
 Widmaier KW-1 Quero Quero
 Widmaier KW-2 Biguá

Widmer
(Hans Widmer / Matheus Avallone Sobrinho & Kurt Hendrich)
 Widmer HW-4 Flamengo (Flamingo)

Wiederkehr
 Wiederkehr GHW-1 Cu-Climber
 Wiederkehr GHW-2

Wiesner
(Jaroslav  Wiesner)
 Wiesner Schrudim

Wikner
(Geoffrey Neville Wikner)
 Wikner Golden Sparrow
 Wikner-Lindner Secondary

Wilkes
 Wilkes BMW-1

Wilkinson
 Wilkinson Mk 1
 Wilkinson Mk 2

Wimmer-Dewald
(Josef Immer & Alexander Dewald)
 Wimmer-Dewald Leonardo 2000

Wind
(Willy Wind)
 Wind Wi-1

Windward Performance
(Greg Cole)
 Windward Performance Perlan II
 Windward Performance SparrowHawk
 Windward Performance DuckHawk
 Windward Performance JetHawk
 Windward Performance GosHawk

Wishart
(Alfred William Wishart)
 Wishart 1930 glider
 Wishart Biplane glider

WLM
(WLM Flugingenieure / Rudolf Sägesser / Isler & Co, Wildegg / H. Sägesser, Flugzeugbbau, Herzogenbuchsee)
 WLM-1
 WLM-2

Wright
(Peter W. Wright)
 Wright Micron
 Wright MPA – man powered aircraft
 Wright Falcon

Wright Bros.
(Wilbur & Orville Wright)
 Wright 1900
 Wright 1901
 Wright 1902
 Wright IV 1911

WS
(Warsztaty Szybowcowe – glider workshops)
 WS SG-3
 WS SG-7
 WS SG-21 Lwów
 WS SG-28
  WS Wrona
 WS Komar
 WS Sroka
 WS Sokol
 WS Mewa
 WS Orlik

WWS
(Wiegand und Wisser Sportflugzeugbau GmbH & Co. KG)
 WWS WM-1

Notes

Further reading

External links

Lists of glider aircraft

redpajama_set_name: RedPajamaWikipedia


text:
Q: Remove comma from citation after connector (&) I am publishing a paper for a convention that asked me to remove the citation commas before & in my quotes. I'm using this conference template and have not customizes anything in the project for citation. It looks like the template is using the apacite citation management package along with myapacite.bst to format citation call-outs and the bibliographic entries themselves.
Whenever I cite like this:
@article{geurts2006extremely,
  title={Extremely randomized trees},
  author={Geurts Pierre and Ernst Damien and Wehenkel Louis},
  journal={Machine learning},
  volume={63},
  number={1},
  pages={3--42},
  year={2006},
  publisher={Springer},
  doi={10.1007/s10994-006-6226-1}
}

\cite{geurts2006extremely}

I get an output such as
(Pierre, Damien, & Louis, 2006)

I am new to latex and am stuck on trying to remove the comma before & and make it look like this:
(Pierre, Damien & Louis, 2006)

Any help is appreciated.

A: The document class you employ loads the apacite package. I suggest you run
\AtBeginDocument{\renewcommand{\BCBT}{} \renewcommand{\BCBL}{}}

in the preamble to achieve your formatting objective. See p. 34 of the user guide of the apacite package for further explanations.
And, you should -- actually, must -- change the author line to
  author={Geurts, Pierre and Ernst, Damien and Wehenkel, Louis},