В докладе мы познакомимся с понятиями систем доказательств и аксепторов для языков. Будет доказана теорема Месснера о том, что существование оптимальных аксепторов эквивалентно существованию p-оптимальных систем доказательств. Вторая часть доклада будет посвящена существованию оптимальных эвристических аксепторов и систем доказательств.