Существует большое количество литературы по «тестированию свойств» - проблеме создания небольшого числа запросов черного ящика к функции чтобы различать два случая:
является членом некоторого класса функций C
является ε -far из каждой функции в классе C .
Диапазон функции иногда является логическим: R = { 0 , 1 } , но не всегда.
Здесь, -far , как правило , следует понимать расстояние Хемминга: доля точек F , которые должны были бы быть изменены , с тем чтобы место F в классе C . Это естественная метрика, если f имеет логический диапазон, но кажется менее естественной, если диапазон, скажем, действительный.
Мой вопрос: существует ли часть литературы по тестированию свойств, которая проверяет близость к некоторому классу относительно других метрик?
Обычно это не называется тестированием свойств (и на самом деле это не так), но есть большая часть работы по определению свойств матрицы, рассматривая небольшой индуцированный минор. Это очень похоже на цель в тестировании свойств. Смотри, например, статью Рудельсона и Вершинина:
http://portal.acm.org/citation.cfm?id=1255449
Есть более ранние работы Frieze-Kannan. Дело в том, что обычно используемая ими метрика представляет собой некоторую матричную норму, такую как спектральная норма, норма Фробениуса или норма отсечки. Если вы хотите, вы можете думать о некоторых из этих результатов как об алгоритмах тестирования свойств в метрике, отличной от расстояния Хэмминга.
источник
источник