Равенство или неравенство классов P и NP для вычислений с оракулом. Задачи поиска для NP-языков. Классы, связанные с задачами поиска, в которых ответ точно есть: PLS, PPAD, PPA, PPP.