\documentclass[12pt]{ib102}
\usepackage[czech]{babel}\usepackage{enumerate}

\setassignment{11}
\setexercise{1}
\setduedate{16}{12}{2013}
\setpoints{2}

%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\setstudent{James Bond}
\setgroup{MI6}
\setuco{007}


\begin{document}
\begin{zadani}
Definujme jazyk \textsc{Triple-SAT} následovně:
\begin{equation*}
\textsc{Triple-SAT} = \{ \,\langle\Phi\rangle \mid \text{Booleovská formule } \Phi \text{ má alespoň 3 různá splňující přiřazení } \}
\end{equation*}
Dokažte, že jazyk \textsc{Triple-SAT} je NP-úplný. Vaší úlohou je tedy ukázat, že \textsc{Triple-SAT} je NP-těžký (nejlépe redukcí z~nějakého jiného NP-těžkého problému) a zároveň, že patří do třídy NP. Použitou redukci co nejpřesněji popište a zdůvodněte, proč se jedná o~polynomiální redukci.
\end{zadani}

\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
