\documentclass[]{vycsloz}
\usepackage[shorthands=off,czech]{babel}

\newcommand{\Nset}{\mathbb{N}}
\newcommand{\range}{\mathit{range}}
\renewcommand{\phi}{\varphi}

\assignment{3}
\exercise{1}
\points{3}
\duedate{8. 12. 2023, 23:59}

%%% ZDE NAPISTE SVOJE UCO A JMENO
\name{Nesmlouvavý Pstruh}
\uco{1234567}

\begin{document}
\begin{zadani}
  Řekneme, že výroková formule $\phi$ v konjunktivní normální formě
  (CNF) je \emph{napůl splnitelná}, právě když existuje valuace splňující
  přesně $\lceil\frac{n}{2}\rceil$ klauzulí formule $\varphi$, kde $n$ je počet
  klauzulí této formule.

  Uvažme problém rozhodnout, zda je daná výroková formule v CNF napůl splnitelná, tedy problém
  \[
    \textit{HALFSAT} = \{\langle \phi \rangle \mid \phi \text{ je formule v CNF, která je napůl splnitelná} \}.
  \]
  Dokažte, že $ \textit{HALFSAT} $ je \textsf{NP}-úplný.
\end{zadani}

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

\end{document}