Na dzisiejszym referacie opowiemy sobie o grafowych bazach danych, powiemy sobie jak z pozoru łatwe problemy grafowe stają się NP trudne w momencie gdy dodamy do nich wyrażenie regularne. Opowiemy sobie o tym jak wybrana semantyka ścieżek wpływa na złożoność obliczeniową problemów, oraz jakie realne konsekwencje niesie to ze sobą.

Zdefiniujemy klasę STE (Simple Transitive Expressions) dla wyrażeń regularnych, i pokażemy na niej ważną zasadę dychotomii która pozwala na dokładniejsze określenie złożoności obliczeniowej danych problemów.