IB107 úkol 3, příklad 2 Odevzdání: 9. 12. 2022, 23:59
Jméno: Nesmáčivá Plotice UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [3 body] Omezenou soustavou rovnic nazveme soustavu lineárních rovnic tvaru
a11x1 + a12x2 + . . . + a1nxn = b1
a21x1 + a22x2 + . . . + a2nxn = b2
...
am1x1 + am2x2 + . . . + amnxn = bm
kde m, n > 0 a všechny lineární koeficienty a11, a12, . . . , amn a absolutní členy b1, b2, . . . , bm jsou nezáporná
celá čísla. Uvažme problém rozhodnout, zda má omezená soustava rovnic řešení x1, x2, . . . , xn ∈
{0, 1}, tedy problém
OSR = { S | S je omezená soustava rovnic, která má řešení využívající pouze hodnot {0, 1}}.
Dokažte, že problém OSR je NP-těžký. (K důkazu můžete využít znalost NP-úplných problémů z přednášky.
Pokud budete chtít využít NP-těžkost nějakého jiného problému, tak ji také dokažte.)
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.