Избыточность и структура вычислительных задач

Широко распространено мнение, что некоторые вычислительные задачи, такие как изоморфизм графов, не могут быть NP-полными, поскольку они не обладают достаточной структурой или избыточностью, чтобы быть вычислительно сложными (NP-трудными). Я заинтересован в различных формальных понятиях для структуры вычислительных задач и мер избыточности.

Какие основные результаты известны о таких формальных понятиях для вычислительных задач? Недавний обзор таких понятий был бы очень хорош.

РЕДАКТИРОВАТЬ: Опубликовано на MathOverflow

На самом деле, я думаю, что феномен здесь заключается в том, что GI в некотором смысле имеет слишком большую структуру. Это в некотором смысле теоретико-групповая природа его свидетелей, которая приводит к алгоритму для GI и является одним из технических доказательств того, почему люди считают, что GI не является N P- неполным. Я думаю, что здесь так много структуры, что проблема «слишком жесткая», чтобы кодировать произвольные задачи N $\mathsf{coAM}$$\mathsf{NP}$$\mathsf{NP}$

Другим способом уловить это является тот факт, что версии GI для подсчета и принятия решений эквивалентны, в то время как для всех известных неполных задач это не так, если только иерархия полиномов не рухнет. Это также можно рассматривать как захват некоторого аспекта структуры / избыточности: для неструктурированных общих проблем подсчет решений кажется гораздо сложнее, чем указание на существование, тогда как обширная структура GI позволяет показать, что подсчет и решение эквивалентны.$\mathsf{NP}$

(С другой стороны, групповой изоморфизм кажется даже более структурированным, чем GI, но для группы iso не известно сокращение подсчета до решения. Возможно, это говорит о том, что GI находится на уровне «просто правильного» уровня структуры - слишком структурирован, чтобы быть NP-полными, но достаточно неструктурированными, чтобы можно было сократить счет до принятия решения.)