Оценка сложности вычисления гиперобъема — различия между версиями
Строка 1: | Строка 1: | ||
− | + | [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Утверждается, что точное вычисление значения гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за | Утверждается, что точное вычисление значения гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за |
Версия 14:15, 19 июня 2012
Утверждается, что точное вычисление значения гиперобъема #P-трудной задачей, однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
множества из точек -мерного пространства является- полином от количество параметров,
- полином от количества решений,
- полином от качества аппроксимации.
#P-трудность задачи вычисления гиперобъема
Доказательство будет состоять в сведении задачи #MON-CNF (Satisfability problem for monotone boolean formulas).
Определение: |
задача #MON-CNF -- задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ | где клозы
Задача #MON-CNF является #P-трудной
Сведем ее к задаче вычисления гиперобъема.
Задача MON-CNF состоит в нахождении количества удовлетворяющих подстановок для
Количество ее удовлетворяющих подстановок равно
минус количество удовлетворяющих подстановок ее отрицания
поэтому далее будем работать с
. Для каждого клоза построим гиперкубгде
например, гиперкубу
будет соответствовать клоз
а
клоз .Заметим, что объединение гиперкубов
может быть записано как объединение гиперкубов вида , где .Более того,
удовлетворяет для некоторого удовлетворяет
Заметим, что так как
удовлетворяетТаким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит #P