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

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

\assignment{3}
\exercise{2}
\points{3}
\duedate{9. 12. 2022, 23:59}

%%% ZDE NAPISTE SVOJE UCO A JMENO
\name{Nesmáčivá Plotice}
\uco{1234567}

\begin{document}
\begin{zadani}
  \emph{Omezenou soustavou rovnic} nazveme soustavu lineárních rovnic
  tvaru
  \[
  \begin{array}{ccccccccc}
    a_{11}x_1 &+& a_{12}x_2 &+& \ldots &+& a_{1n}x_n&=&b_1\\
    a_{21}x_1 &+& a_{22}x_2 &+& \ldots &+& a_{2n}x_n&=&b_2\\
              &&&&&&&\vdots&\\
    a_{m1}x_1 &+& a_{m2}x_2 &+& \ldots &+& a_{mn}x_n&=&b_m\\
  \end{array}
  \]
  kde $m,n>0$ a všechny lineární koeficienty $a_{11},a_{12},\ldots,a_{mn}$ a absolutní členy $b_1,b_2,\ldots,b_m$ jsou nezáporná celá čísla.
  %, tedy $a_{11},a_{12},\ldots,a_{mn},b_1,b_2,\ldots,b_m\in\Nset_0$.
  Uvažme problém rozhodnout, zda má omezená soustava rovnic řešení $x_1,x_2,\ldots,x_n\in\{0,1\}$, tedy problém 
  \[
    \textit{OSR} = \{\langle S \rangle \mid S \text{ je omezená soustava rovnic, která má řešení využívající pouze hodnot }\{0,1\}\}.
  \]
  Dokažte, že problém $\textit{OSR}$ je \textsf{NP}-těžký.
  \emph{(K důkazu můžete využít znalost \textsf{NP}-úplných problémů z~přednášky. Pokud budete
    chtít využít \textsf{NP}-těžkost nějakého jiného problému, tak ji také dokažte.)}
\end{zadani}


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

\end{document}
