\documentclass{ib102}
\usepackage[shorthands=off,czech]{babel}
\usepackage{amsmath}
% vim: fo+=t tw=80 spell spelllang=cs
% gen: ready

\assignment{12}
\exercise{1}
\points{2}
\duedate{19. 12. 2016}

\newcommand{\anfsat}{\ensuremath{\mathrm{ANF\textnormal{-}SAT}}}
\newcommand{\afsat}{\ensuremath{\mathrm{AF\textnormal{-}SAT}}}
\newcommand{\NP}{\ensuremath{\mathsf{NP}}}
\newcommand{\enc}[1]{\ensuremath{\langle #1 \rangle }}

%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\name{}
\group{}
\uco{}


\begin{document}
\begin{zadani}
Definujme jazyk \anfsat~následovně:
\[
\anfsat = \{ \enc{\varphi} \mid \varphi \text{ je splnitelná formule v ANF} \}
\]

\noindent
Výroková formule je v ANF, pokud obsahuje pouze konjunkce, negace a výrokové
    proměnné. Příklad formule v ANF:
    \[
        a \wedge \neg ( b \wedge c \wedge \neg(a \wedge \neg c ) )
    \]
Dokažte, že jazyk \anfsat~je \NP-úplný. Vaší úlohou je tedy ukázat, že
\anfsat~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}
