\documentclass[a4paper]{slides}
%\documentclass[a4paper,draft]{slides}
\usepackage[dvips]{epsfig,color}
\textwidth=0.85\paperwidth
\textheight=0.9\paperheight
\oddsidemargin=-1cm
\evensidemargin=-1cm
\topmargin=-2.2cm
\pagestyle{empty}
\newcommand{\bs}{\begin{slide}}
\newcommand{\es}{\end{slide}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\bsc}{\begin{slide}\begin{center}}
\newcommand{\esc}{\end{center}\end{slide}}
\newcommand{\bt}{\begin{tabular}}
\newcommand{\et}{\end{tabular}}
\newcommand{\bfr}{\begin{flushright}}
\newcommand{\efr}{\end{flushright}}
\newcommand{\bfl}{\begin{flushleft}}
\newcommand{\efl}{\end{flushleft}}
\newcommand{\Cn}{\color{black}}
\newcommand{\Cr}{\color{red}}
\newcommand{\Cb}{\color{blue}}
\newcommand{\Cv}{\color{green}}
\newcommand{\Cm}{\color{magenta}}
\newcommand{\Cc}{\color{cyan}}
\newcommand{\Cg}{\color{yellow}}
%\onlyslides{3-99}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
\mbox{}
\vspace{2cm}
\Cr
OPTIMIZATION AND\\
STATISTICAL MECHANICS
\vspace{3cm}
\Cn
Federico RICCI TERSENGHI\\
(Univ. ``La Sapienza'', Roma)
\vspace{4cm}
\ec
\Cv
In collaboration with
\vspace{.5cm}\\
\Cb
Silvio Franz (ICTP)\\
Michele Leone (SISSA/ICTP)\\
Marc M\'ezard (Orsay)\\
Andrea Montanari (ENS, Paris)\\
Martin Weigt (G\"ottingen)\\
Riccardo Zecchina (ICTP)
\Cn
\vfill
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
\Cr Two old decision problems
\rule{\textwidth}{1mm}
\Cb Eulerian circuits (1736)
\ec
\epsfig{file=euler.eps,width=\textwidth}
\Cn{\small The seven bridges of K\"onisberg \hfill The equivalent graph}
\vfill
\bc
\Cb Hamiltonian cycles (1859)
\ec
\epsfig{file=hamilton.eps,width=\textwidth}
\mbox{ }\hspace{.5cm}\Cn{\small The dodecahedron \hspace{3cm}
The equivalent graph}
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
\Cr Computer Science: computational complexity
\rule{\textwidth}{1mm}
\ec
\Cn
Classifying problems according to the computational resources required
for their solution (e.g.\ CPU time and memory) in the {\Cr worst case}.
{\Cb tractable} (in {\Cr P}) $\leftrightarrow$ sub-exponential:
{\Cb$\ln(N)$}, {\Cb$N^\alpha$}\\
{\Cb intractable} (in {\Cr NP}) $\leftrightarrow$ exponential:
{\Cb$2^N$}, {\Cb$N!$}\\
\mbox{ }\hfill{\small {\Cb$N$} is the number of variables in the problem.}
\vfill
\centering\underline{\Cr Main Complexity Classes}
\bfl
{\Cr P\ \ } = polynomial\\
{\Cr NP} = non-deterministic polynomial\\
\efl
\vspace{-0.7cm}
\centering{$\Downarrow$}
\vspace{-0.7cm}
\bfr
\begin{tabular}{ll}
$\bullet\!\!\!$ & non-determ. algorithms: {\tt goto both}\\
$\bullet\!\!\!$ & succinct certificate
\end{tabular}
\vfill
\epsfig{file=np-alg.eps,width=0.7\textwidth}
\efr
\bfl
\vspace{-7cm} {\Cr P = NP ?}\\ {\small \mbox{}\\ First
Millennium\\Prize Problem\\}
\vspace{2cm} {\small \Cv Quantum\\ computation !}
\efl
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr NP-completeness: combinatorial optimization
\rule{\textwidth}{1mm}}
{\Cb THEOREM}: All problems in {\Cr NP} are polynomially reducible to
{\Cr $K$-SAT} ($K>2$). (Cook, 1971)
{\bf NP-complete} are the {\Cr hardest} {\bf NP} problems.
\epsfig{file=np-map.eps,width=0.9\textwidth}
\underline{Beyond {\Cr NP}}
\begin{tabular}{ll}
$\bullet$ & $\left\{\begin{tabular}{l} decision\\ evaluation\\
optimization \end{tabular} \right\}$ problems ({\Cr NP-hardness})\\
$\bullet$ & {\Cb counting} problems ({\Cr \#P},{\Cr \#P-complete}):\\
& e.g.\ \#SAT counts the entropy of SAT.
\end{tabular}
\esc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr Some interesting problems
\rule{\textwidth}{1mm}}
\underline{\Cr SAT}
\ec
Boolean variables: {\Cb$x_i \in \{0,1\} \quad i=1,\ldots,N$}\\
Logical operators: {\Cb$\overline{\;\cdot\;}=\mbox{NOT}{\Cn,}\
\vee=\mbox{OR}{\Cn,}\ \wedge=\mbox{AND}$}\\
Given a Boolean formula like\\
{\Cb$(x_1 \vee x_{27} \vee \bar x_3) \wedge (\bar x_{11} \vee x_2)
\wedge \ldots \wedge (\bar x_{21} \vee x_9 \vee \bar x_8 \vee \bar
x_{30})$}\\
decide if a {\Cr satisfying} truth assignment exist
\underline{Random 3-SAT}: 3 random literals per clause\\
\mbox{} \hspace{6cm}\# clauses = $\alpha\: N$
\centering\underline{\Cr Coloring}\\
\parbox{0.48\textwidth}{
\underline{$q$-coloring on graphs}:\\
2-coloring $\in$ P\\
3-coloring $\in$ NP-c\\
}
\epsfig{file=coloring.eps,width=0.5\textwidth}
\parbox[b]{0.55\textwidth}{
\underline{Bicoloring on hypergraphs}:\\
NP-complete\\
}
\epsfig{file=color_hyper.eps,width=0.42\textwidth}
\vfill
\bt{r|l}
\Cb Computer Science & \Cb Physics \\ \hline
$K$-SAT & Diluted Ising Spin Glasses \\
Graph Coloring & Potts Models \\
Vertex Cover & Hard Spheres \\
... & ...
\et
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr Worst-case vs.\ Typical-case
\rule{\textwidth}{1mm}}
{\Cb Real-world NP-complete and \#P-complete problems may have many
easy instances}
Ensemble of random NP-complete problems hard {\Cr on average} (e.g.\
random 3-SAT)
\underline{\Cr Random models: phase transitions, NP-hardness}
\epsfig{file=tempi.eps,angle=270,width=0.7\textwidth}
{\bf Onset of complexity} $\leftrightarrow$ {\bf Phase transition}
SAT/UNSAT transition: {\Cb $E=$ \# violated clauses} becomes greater
than zero.
{\Cr What makes problems hard close to $\alpha_c$?}
\esc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr Mapping to a Statistical Mechanics problem
\rule{\textwidth}{1mm}}
\ec
{\Cb Zero temperature} limit of a {\Cr diluted} mean-field spin
model. Much harder than usual fully connected!
For \underline{\Cr random 3-SAT}, with $s_i = (-1)^{x_i}$,
\Cb\[
{\cal H} = \frac18 \left( \alpha N -\!\sum_{i=1}^N H_i s_i
+\!\sum_{i2$).
Two versions of the model:\vspace{.3cm}\\
\begin{tabular}{rl}
$\bullet$ & {\Cr unfrustrated}, ferromagnetic: {\Cb$J_{ijk}=1$}\\
& $\rightarrow$ 1$^{\mbox{st}}$ order ferromagnetic transition\\
$\bullet$ & {\Cr frustrated}, spin glass: {\Cb$J_{ijk}=\pm1$}\\
& $\rightarrow$ SAT/UNSAT transition\\
\end{tabular}
\Cr Both versions have a glassy phase!
\vfill
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr Zero-temperature phase diagram
\rule{\textwidth}{1mm}}
\ec
Any {\Cb$p>2$} and {\Cb fluctuating connectivity} hypegraphs.
Analytic solution and numerics:\\
if {\Cb$E=0$} (no frustration) $\rightarrow$ {\Cr Gaussian
elimination}
if {\Cb$E>0$} $\rightarrow$ {\Cr exhaustive enumerations}
\epsfig{file=sol_space.eps,width=\textwidth}
Configurational entropy: {\Cb$\Sigma(\gamma) = \frac1N \ln(\mbox{\#
clusters})$}
{\Cr A common problem}\\
{\Cr$\bullet$} {\Cb diluted p-spin} glass at $T=0$\\
{\Cr$\bullet$} random {\Cb p-XOR-SAT} $^\S$\\
{\Cr$\bullet$} low density {\Cb Parity Check codes}\\
{\Cr$\bullet$} random {\Cb linear systems} in finite fields ({\Cb GF[2]})\\
$^\S$ {\small considered an open problem in theoretical computer science}
\vfill
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
\epsfig{file=hsat_plot1.ps,width=\textwidth}
\esc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr The structure of the configurational space
\rule{\textwidth}{1mm}}
\epsfig{file=states.eps,width=\textwidth}
Starting from a {\Cr random} configuration, both models have the same
{\Cb off-equilibrium dynamics}
\underline{\Cr Phase diagram}
\epsfig{file=crit_lines_color.eps,width=0.85\textwidth}\\
\vspace{0.4cm}
{\small $T$ is the temperature and $3\gamma$ is the average
connectivity}
\esc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
\Cr Static and dynamic limits do not coincide!
\rule{\textwidth}{1mm}
\Cn
\epsfig{file=landscape.eps, width=0.9\textwidth}
\ec
$\bullet$ {\Cr Static} limit: {\Cb $t \to \infty$} {\Cr before} {\Cb
$N \to \infty$}
For any finite size and for any ergodic dynamics the system relaxes to
the {\Cr ferromagnetic minimum} (in a time which is exponentially
large in $N$).
$\bullet$ {\Cr Dynamic} limit: {\Cb $t \to \infty$} {\Cr after} {\Cb
$N \to \infty$}
For an infinite sized system the time to escape from a metastable
state is infinite and thus the system relaxes to the {\Cv higher
energy} ($E_{Th}$) {\Cv metastable state} and get trapped there
forever.
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
\epsfig{file=cool_heat.ps,width=\textwidth}
\esc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr Conclusions and perspectives
\rule{\textwidth}{1mm}}
\ec
\underline{\Cb New results}\\
{\small
$\bullet$ $p$-spin ($p>2$) with fluctuating connectivity\\
$\rightarrow$ structure of the configurational space:
$\gamma_d$, $\gamma_c$ and $\Sigma(\gamma)$\\
$\rightarrow$ $\gamma_c$ is the exact threshold for random p-XOR-SAT\\
$\rightarrow$ new transitions in random hypergraphs\\
$\bullet$ $p$-spin ($p>2$) and Bicoloring with fixed connectivity\\
$\rightarrow$ exact 1-RSB solution: GS energy\\
$\bullet$ $K$-SAT and Bicoloring\\
$\rightarrow$ variational bounds for $\alpha_c$ (at present the
best!)\\
$\rightarrow$ very good benchmark for SAT solvers\\
}
\underline{\Cb Some applications}\\
{\small
$\bullet$ test-bed for heuristic algorithms: GS energy\\
$\bullet$ dynamical transitions in Coding and Cryptography\\
$\bullet$ solvable models for glassy systems and granular matter\\
}
\underline{\Cb Examples of open issues}\\
{\small
$\bullet$ complete 1-RSB and FRSB theories (with correlations)\\
$\bullet$ out of equilibrium dynamics\\
$\bullet$ analysis of randomized algorithms\\
$\bullet$ better analysis of the configurational space in $K$-SAT\\
}
\es
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsc
{\Cr Some references
\rule{\textwidth}{1mm}}
\ec
{\small
\begin{itemize}
\item {\Cb Simplest introduction to Computational Complexity:}\\
S.~Mertens, {\it ``Computational Complexity for Physicists''},
cond-mat/0012185.
\item {\Cb NP-completeness and Computational Complexity:}\\ M.R.~Garey
and D.S.~Johnson, {\it ``Computers and Intra\-ctability. A guide to
the theory of NP-completeness''} (Freeman, San Francisco, 1979).\\
C.H.~Papadimitriou, {\it ``Computational Complexity''}\\
(Addison-Wesley, Reading, MA, 1994).
\item {\Cb Phase transition in $K$-SAT:}\\
S.~Kirkpatrick and B.~Selman, Science {\bf 264}, 1297 (1994).
\item {\Cb Statistical Mechanics of $K$-SAT:}\\
R.~Monasson and R.~Zecchina, Phys. Rev. Lett. {\bf 76}, 3881 (1996);
Phys. Rev. E {\bf 56}, 1357 (1997).
\item {\Cb Typical-case complexity:}\\
R.~Monasson, R.~Zecchina, S.~Kirkpatrick, B.~Selman and L.~Troyansky,
Nature {\bf 400}, 133 (1999).
\item {\Cb Hyper-SAT:}\\
F.~Ricci-Tersenghi, M.~Weigt and R.~Zecchina, Phys. Rev. E {\bf 63},
026702 (2001).
\item {\Cb 3-spin at finite temperatures:}\\
S.~Franz, M.~M\'ezard, F.~Ricci-Tersenghi, M.~Weigt and R.~Zecchina,
Europhys. Lett. {\bf 55}, 465 (2001).
\item {\Cb Exact solution for 3-spin at $T=0$:}\\
S.~Franz, M.~Leone, F.~Ricci-Tersenghi and R.~Zecchina,
Phys. Rev. Lett. {\bf 87}, 127209 (2001).
\end{itemize}
}
\es
\end{document}