Problemy trudne obliczeniowo — Zadania

Czȩść druga

Damian Niwiński

Kwiecień 2001

Zadania punktowane

1. (3 pt) Udowodnić, że problem niepustości, tj. pytanie L(α) ≠ ∅ ? dla wyrażeń regularnych z przeci_{}eciem jest w klasie PSPACE.

Uwaga. Wyrażenia regularne z przeci_{}eciem nad alfabetem Σ określamy, podobnie jak zwykłe wyrażenia regularne, jako najmniejszy zbiór zawieraj _{}acy ∅ i σ, dla σ ∈ Σ, oraz zamkni_{}ety na operacj_{}e konkatenacji, +, ∗ i, dodatkowo, ∩. J_{}ezyk L(α) ⊆ Σ^{∗} określony przez wyrażenie regularne α jest zdefiniowany analogicznie jak dla zwykłych wyrażeń z tym, że ponadto L(α ∩ β) = L(α) ∩ L(β).

Z wykładu wynika, że interesuj _{}acy nas problem jest trudny w klasie PSPACE (a zatem jest PSPACE–zupełny). Analogiczny problem dla zwykłych wyrażeń jest rozstrzygalny w czasie wielomianowym, a dla wyrażeń z przeci_{}eciem i operacj _{}a dopełnienia — jest rozstrzygalny, ale jedynie w czasie nieelementarnym.

2. (2 pt) Udowodnić, że dla każdej maszyny Turinga M z jedn _{}a taśm _{}a rozpoznaj _{}acej j_{}ezyk {w$w : w ∈ {0, 1}^{∗}}, istnieje stała d_{M}, że dla nieskończenie wielu słów obliczenie akceptuj _{}ace wymaga co najmniej d_{M}n^{2} kroków (gdzie n jest długości _{}a wejścia).