Ну если

произвольное и

зависит от арности функции, то да.
Если брать

быстро вычислимым, а

полиномиальным, то нет. (Все задачи такого вида лежат в coNP).
Вот, скажем, выполнимость (

)- NP-полная задача. Если бы она лежала в coNP, то NP=coNP. Это не доказано, и специалисты считают, что скорее всего неверно.
-- Пн май 17, 2010 22:38:18 --Вы попробуйте получше формализовать Вашу задачу про вероятностные оценки, а мб тоже что-нибудь подскажу.
Что-то я плохо это понял. Я ведь недозагружен теорией.
И не помню что такое "coNP". Но это я найду в интернете.
Что такое "арность", и к чему относятся "да", "нет"?
Разве (

) не то же самое, что проверить на тавтологию?
Арность, местность - количество аргументов функции.
Тавтология - это

, а

- это выполнимость.
"Да" и "нет" относится к следующему - любое свойство булевой функции

можно представить в виде

, но

здесь может быть очень большим, а

- очень сложной. Например,

, т.е. здесь

и не очень понятно, можно ли его уменьшить.
Если поставить условие, что

(не больше некоторого полинома), а функция

вычисляется полиномиальным алгоритмом, то в виде

представляются только coNP-свойства.
Ну и про NP и coNP я все-таки напишу. NP - это класс свойств, для которых существует сертификат принадлежжности, то есть мы можем быстро проверить, удовлетворяет ли объект NP-свойству, если задана некоторая доп. информация. А coNP - это те, для которых существует сертификат отвергающий, т.е. можно быстро проверить, что функция классу не принадлежит. Разумеется, если задача проверки некоторого свойства S лежит в NP, то задача проверки того, что объект не обладает этим свойством, лежит в coNP.
Например, в случае тавтологии можно легко проверить, что функция не тавтология, если задан набор, где она равна 0. А в случае выполнимости можно легко проверить, что функция выполнима, если задан набор, где она 1. Значит, тавтология - задача из coNP, а выполнимость - NP. Считается более правдоподобным, что NP не равно coNP, поэтому NP-полные свойства вряд ли можно представить в виде (1)
В принципе, можно проверить и более сложные свойства, которые, скорее всего, не будут лежать ни в NP, ни в coNP.