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

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

\assignment{3}
\exercise{2}
\points{3}
\duedate{7. 12. 2021, 23:59}

%%% ZDE NAPISTE SVOJE UCO A JMENO
\name{Noblesní Plšice}
\uco{1234567}

\begin{document}
\begin{zadani}
  Uvažme problém pro danou gramatiku $\cG$ typu 0 (tedy bez omezení) a
  dané $k\in\Nset$ rozhodnout, zda lze v této gramatice odvodit
  prázdné slovo $\varepsilon$ v nejvýše $k$ krocích. Problém nazveme
  \emph{bounded epsilon derivation} a ztotožníme s množinou
  \[
  \textit{BED} = \{\langle \cG,k \rangle \mid \cG\text{ je gramatika splňující }S\stackrel{\le k}{\Longrightarrow}_\cG\varepsilon\text{, kde $S$ je kořenem }\cG\}.
  \]
  Dokažte, že problém \textit{BED} je \textsf{NP}-těžký.  
\end{zadani}

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

\end{document}