Есть действительно хорошие ответы на этот конкретный вопрос, поэтому нет смысла писать собственное объяснение. Таким образом, я постараюсь внести свой вклад в отличный ресурс о различных классах вычислительной сложности.
Для тех, кто считает, что вычислительная сложность - это только P и NP, - самый исчерпывающий ресурс о проблемах с вычислительной сложностью. Помимо проблем, заданных ОП, в нем перечислены примерно 500 различных классов вычислительных задач с красивыми описаниями, а также список фундаментальных исследовательских работ, описывающих класс.