Zápočtová písemka - zadání
Napsal: 12. 1. 2012 17:50
Zadání zápočtovky (ne že by to bylo něco nového - opravdu úlohy z cvičení):
1) Ukažte, že TAUT je co-NP; jaká je složitost TAUT DNF?
2) Složitost hledání cesty v grafu se zápornými hranami.
3) Polynomiální algoritmus pro nalezení opt vrcholového pokrytí acyklického grafu.
1) Ukažte, že TAUT je co-NP; jaká je složitost TAUT DNF?
2) Složitost hledání cesty v grafu se zápornými hranami.
3) Polynomiální algoritmus pro nalezení opt vrcholového pokrytí acyklického grafu.