Je tu niekto kto by si vedel poradiť s niečím podobným a má zhruba 2 hodiny čas?
1) Ktoré z nasledovných výrokov sú pravdivé? Pár slovami vysvetliť prečo....
A) Problém zistiť, či dané slovo w patrí do jazyka definovaného pomocou konečného automatu možno zistiť v polynomiálnom čase vzhľadom na veľkosť vstupu
B) Existuje funkcia, ktorá je rekurzívna, ale nie P.R.
C) Problém zistiť, či každé riešenie PCP dĺžky <= k je algoritmicky riešiteľný.
D) Každý nedeterministický polynomiálny problém možno redukovať na SAT.
2)
Dokážte, že funkcia PRNO(n), ktorá vypočíta n-TB´ prvočíslo je primitívne rekurzívna.
3)
Dokážte, že funkcia najmenší spoločný násobok N.S.N (a,b) je primitívne rekurzívna môžete použiť, že +,-,* sú prim.rek.
4) Nájdite úplne primitívne rekurzívne odvovodnenie charakteristickej funkcie predikátu ∃x (y=x^2)
Správa, iba seriózne......
Za kvalitu zaplatím.........