Таким образом, PCP является полуразрешимым и неразрешимым, а проблема остановки - неразрешимой. Можно ли даже назвать временную сложность для них, например NP или expTime?
А как насчет космической сложности: они в Pspace?
Так как @walnut заявил, что они не входят ни в один из упомянутых классов сложности, потому что классы требуют наличия алгоритма, который решает проблему в первую очередь. Спасибо за ваш ответ :)