Complexity and consistency of statistical criteria

В статье рассматривается связь состоятельности статистических критериев и асимптотической сложности их вычисления в случае конечных пространств. Показано, что из заданной состоятельной последовательности критериев можно построить другую состоятельную последовательность, для которой сложность вычисления принадлежности наблюденных значений к критическим множествам этих критериев асимптотически мала по сравнению с аналогичной сложностью для исходных критериев. Однако такое упрощение по сути оказывается фиктивным. Для того, чтобы не допускать фиктивного упрощения вычисления принадлежности наблюденных значений к критическим множествам в последовательности критериев, необходимо накладывать дополнительные ограничения на классы рассматриваемых критериев. В статье показано, что в случае естественных ограничений упрощение вычисления может привести к нарушению свойства состоятельности последовательности критериев. Приведены оценки эффективности использования двухступенчатых критериев, когда сначала работают простые, но не состоятельные в заданном классе альтернатив критерии, и только в случае непринятия гипотезы применяются сложно вычислимые критерии для всего класса альтернатив.