Измерение случайности формул CNF

12

Широко известно, что формулы CNF можно условно разделить на 2 широких класса: случайный и структурированный. Структурированные формулы CNF, в отличие от случайных формул CNF, демонстрируют некоторый порядок, демонстрируя паттерны, которые вряд ли могут произойти случайно. Тем не менее, можно найти структурированные формулы, показывающие некоторую степень случайности (т.е. определенные конкретные группы предложений кажутся гораздо менее структурированными, чем другие), а также случайные формулы с некоторой слабой структурой (то есть определенные конкретные группы предложений кажутся менее случайными, чем другие ). Следовательно, кажется, что случайность формулы - это не просто факт да / нет.

Пусть будет функцией, которая, учитывая формулу CNF , возвращает действительное значение в диапазоне от до включительно: означает чисто структурированную формулу, в то время как означает чисто случайную формулу.F F 0 1 0 1r:F[0,1]FF0101

Интересно, пытался ли кто-нибудь когда-нибудь изобрести такой . Конечно, значение, возвращаемое , будет (по крайней мере, моим намерением) просто практическим измерением согласно некоторым разумным критериям, а не твердой теоретической правдой.рrr

Мне также интересно узнать, определял ли кто-либо когда-либо какой-либо статистический показатель, который можно использовать при определении или при определении других полезных общих свойств формулы. Под статистическим показателем я имею в виду нечто подобное:r

  1. HCV (Hit Count Variance)

    Пусть функция , что, учитывая переменную , возвращает число раз появляется в . Пусть множество переменных , используемых в . Пусть будет AHC (средний попаданий). HCV определяется следующим образом: v jN v j F V F ˉ h F = 1hF:NNvjNvjFVFНУС=1h¯F=1|V|vjVhF(vj)

    HVC=1|V|vjV(hF(vj)h¯F)2

    В случайных случаях HCV очень низок (все переменные упоминаются почти одинаковое количество раз), тогда как в структурированных случаях это не так (некоторые переменные используются очень часто, а некоторые нет, то есть существуют «кластеры использования» ).

  2. AID (средняя степень ).

    Пусть будет количеством раз, когда положительным, и пусть число раз, когда оно отрицательным. Пусть будет функцией, которая, учитывая переменную , возвращает свой идентификатор (степень загрязненности). Функция определяется следующим образом: . Те переменные, которые встречаются в половине случаев положительных и в половине раз отрицательных, имеют максимальную степень загрязненности, в то время как переменные, встречающиеся всегда положительно или всегда отрицательно (т.е. чистые литералы), имеют минимальную степень примеси. AID просто определяется следующим образом: v j h - F ( v j ) i : N[ 0 , 1 ] v jVhF+(vj)vjhF(vj)i:N[0,1]vjVя ( v J ) = 2 м я н ( ч + Р ( v j ) , h - F ( v j )i(vj) AID=1i(vj)=2min(hF+(vj),hF(vj))hF(vj)

    0,511AID=1|V|vjVi(vj)

    В случайных случаях (по крайней мере в случаях, порожденных отрицанием переменных с вероятностью ), AID почти равен в то время как в структурированных случаях оно обычно далеко от .0.511

  3. IDV (дисперсия степени загрязненности)

    IDV является более надежным индикатором, чем один AID, поскольку он учитывает случайные случаи, генерируемые путем отрицания переменных с вероятностью, отличной от . Он определяется как: В случайных случаях IDV равен (поскольку каждая переменная отрицается с той же вероятностью), в то время как в структурированных случаях это далеко от . I D V = 10.5

    00IDV=1|V|vjV(i(vj)AID)2

    00

Мотивы

  1. Чтобы лучше понять, как работают формулы CNF, как можно измерить их случайность / структуру, можно ли вывести другие полезные общие свойства, посмотрев на их статистические показатели, если и как такие показатели можно использовать для ускорения поиска.
  2. Интересно, можно ли сделать вывод о соответствии (или даже количестве решений) формулы CNF, просто умело манипулируя ее статистическими показателями.

Вопросов

  1. Кто-нибудь когда-нибудь предлагал способ измерения случайности формулы CNF?
  2. Кто-нибудь когда-либо предлагал какой-либо статистический показатель, который можно использовать для изучения или даже для механического вывода полезных общих свойств формулы CNF?
Джорджио Камерани
источник
1
см. статью в этом ответе ( cstheory.stackexchange.com/questions/4321/… ). Это может дать вам совет о том, как определить такой г
Маркос Вильягра
1
возможно актуальное обсуждение по измерению случайности цепочек битов mathoverflow.net/questions/37518/…
Ярослав Булатов
Я могу сказать вам так много, так как некоторое время я работал над этим сам. Если вы рассматриваете SAT, формулы для 1 и 2 являются экспоненциальными. С другой стороны, для k-SAT формулы для 1 и 2 являются полиномиальными. Это относится к моему ТОЧНОМУ ОПРЕДЕЛЕНИЮ СЛУЧАЙНОГО ВОПРОСА K-SAT, на который, похоже, никто не хочет отвечать.
Tayfun Pay
@Geekster: Вы хотели бы дать ответ здесь?
Сянь-Чи Чанг 之 之
@Geekster: Что вы подразумеваете под "... формулы для 1 и 2 экспоненциальные" ?
Джорджио Камерани

Ответы:

3

Я предлагаю позаимствовать физическую интуицию, чтобы «менее случайные» структуры были более симметричными. Симметрия для CNF - это любое преобразование переменных, которое сохраняет функцию инвариантной. По этим критериям, функции 3 переменных, таких как

x1x2x3.

или, скажем,

(x1x2¬x3)(x1¬x2x3)(¬x1x2x3)(¬x1¬x2¬x3).

менее случайны, чем, скажем,

(x1x2¬x3)(x1¬x2x3)(¬x1¬x2x3).

В общем, определение понятия «случайный» на конечных структурах является сложной задачей. Исторически, это было опробовано на двоичных последовательностях, которые, возможно, являются простейшими конечными структурами. Например, интуитивно понятно, что последовательность 01010101 является «менее случайной», чем, скажем, 01001110. Однако было быстро понято, что нет последовательного формального определения конечной случайной последовательности! Следовательно, нужно скептически относиться к любым наивным попыткам определить меру случайности для любой конечной структуры.

Тегири Ненаши
источник
Я полностью согласен с интуицией «структура означает наличие симметрий, тогда как случайность означает отсутствие симметрий» . Вы ссылаетесь на синтаксические симметрии (тогда как семантические симметрии - это те, которые изменяют функцию, но оставляют пространство решения без изменений). Я всегда был убежден, что симметрия является ключом.
Джорджио Камерани
1
@Walter: идея симметрии - это попытка использовать алгебру, а не алгоритмы: алгоритмическая сложность - это мера, которая не поддается согласованному определению для конечных объектов. Но затем мы должны назначить меру сложности каждому элементу группы (например, преобразование, которое отрицает одну переменную, проще, чем то, которое отрицает две) - это похоже на простое решение проблемы ...
Тегири Ненаши