- L even = { w e ?*| E !=w, w consists of an even number of symbols}
a) Czy L odd jest takze rozstrzygajacy(decidable) i dlaczego?
b)w jakiej czasowej(time) klasie zlonosci jest L odd?
c)w jakiej przestrzennej(space) klasie zlonosci jest L odd?
d)jakie sa odpowiednie wyniki tych jezykow
zadanie jest po angielksu wiec moje tlumaczneie moze byc nieadekwatne, nie zabardzo rozumiem to zadanie:(
- podaj jezyk L akceptowany przez niedetermistyczna MT (NDMT) ktora jest ograniczona przestrzennie przez 3 do n
a) czy L moze byc takze zaakceptowany przez DMT
b) czy L moze byc takze zaakceptowany przez DMT ktora sie zawsze zatrzymuje(terminate)
i tu jak mi sie wydaje, poniewaz NDTM jest ograniczona przez 3^n to DTM moze sie nigdy nie zatrzymac bo moze uzyc wiecej tasmy(dzialac w nieskonczonosc na niej podczas gdy NDMT zwroci blad) wiec dla mnie odpowiedz na pytanie b)brzmi nie, a)tak bo nie ma warunku ze musi zwrocic jakis wynik
c)czy dopelnienie L jest rozstrzygalne?
d)przypuszczajac ze nie ma wielomianowego ograniczenia na NDTM ktora akceptuje L pokaz ze L nie nalezy do NP
i tu c,d nie mam pojecia jak to ugrysc!:]