의사 부울 함수

수학과 최적화에서 사이비 부울함수는 형태의 함수다.

${\displaystyle f:\mathbf {B} ^{n}\to \mathb {R},}$

여기서 B = {0, 1}은(는) 부울 도메인이고 n은 함수의 아리티라고 불리는 음이 아닌 정수다.부울 함수는 특별한 경우로서 값도 0 또는 1로 제한된다.

표현

모든 의사 부울 함수는 다선형 다항식으로 고유하게 쓸 수 있다.^[1][2]

${\displaystyle f({\boldsymbol{x}}=a+\sum _{i}a_{ij_{ij}x_{j}x}+\sum _{i<j<k}a_{ij}x_{j}x_{j}x_{j}x_{j}x}\ldots}}}}}}}}}}.$

사이비 부울 함수의 정도는 단순히 이 표현에서 다항식의 정도일 뿐이다.

In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function ${\displaystyle f}$ that maps ${\displaystyle \{-1,1\}^{n}}$ to ${\displaystyle \mathbb {R} }$. Again in this case we can uniquely write ${\displaystyle f}$ as a multi-linearpolynomial: ${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}$ where ${\displaystyle {\hat {f}}(I)}$ are Fourier coefficients of ${\displaystyle f}$ and ${\displaystyle [n]=\{1,...,n\}}$.

최적화

유사 부울 함수를 최소화(또는 동등하게, 최대화)하는 것은 NP-hard이다.예를 들어, 최대 절단 문제를 의사 부울 함수를 최대화하는 것으로 공식화하면 이를 쉽게 알 수 있다.^[3]

수하성

서브모듈러 세트 함수는 조건과 동등한 사이비 부울 함수의 특수 클래스로 볼 수 있다.

${\displaystyle f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}}),\;\forall {\boldsymbol {x}},{\boldsymbol {y}}\in \mathbf {B} ^{n}\,.}$

이것은 다항식 시간에 최소화할 수 있기 때문에 사이비 부울 함수의 중요한 클래스다.서브모듈라 함수의 최소화는 NP-hard, Alexander Schrijver(2000)인 서브모듈라 함수의 최대화와 반대되는 페수도-부울 다항식의 경우, 프레젠테이션 양식에서 독립적으로 해결할 수 있는 다항식 문제라는 점에 유의한다.

지붕 이중성

f가 2차 다항식인 경우 지붕 이중성이라는 개념을 사용하여 최소값에 대한 하한을 얻을 수 있다.^[3]지붕 이중성은 또한 변수의 부분적인 할당을 제공할 수 있으며, 다항식에 대한 미니마이저 값의 일부를 나타낼 수 있다.하한을 얻는 여러 가지 다른 방법들이 개발되어 후에야 현재 지붕 이중성이라고 불리는 것과 동등한 것으로 나타났다.^[3]

4분법

f의 정도가 2보다 크면 항상 감소를 채택해 추가 변수와 동등한 2차 문제를 얻을 수 있다.한 가지 가능한 감소는

${\displaystyle \displaystyle -x_{1}x_{2}x_{2}x_{3}=\min _{z\in \mathbf {B}} }z(2-x_{1}-x_{2}-x_{3}}}}}}}}}}}$

예를 들어 다른 가능성도 있다.

${\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{1}x_{1}x_{1}x_{1}+x_{1}.}$

감소가 다르면 결과가 달라진다.다음과 같은 입방체 다항식을 예로 들어보자.^[4]

${\displaystyle \displaystyle f({\jamsymbol {x}=-2x_{1}+x_{2}-x_{3}+4x_{1}+1x_{2}+4x_{1}}x_{3}-2x_{2}x_{3}-2x_{1}x_{1}x_{2}x_{3}.}$

지붕 이중성에 이은 첫 번째 축소를 사용하여 -3의 하한을 얻으며 세 변수를 할당하는 방법에 대한 표시를 하지 않는다.두 번째 감소를 사용하여 -2의 (긴축) 하한과 모든 ${\displaystyle \mathrm{변수}(}$즉 (0, 1, 1$){\$1,1)})의 최적 할당을 얻는다.$$

다항식 압축 알고리즘

Consider a pseudo-Boolean function ${\displaystyle f}$ as a mapping from ${\displaystyle \{-1,1\}^{n}}$ to ${\displaystyle \mathbb {R} }$. Then ${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.$$}}$ ${\displaystyle 각}$ 계수 $f{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ (${\displaystyle }$I${\displaystyle }$) ${\displaystyle {\f}(I)}$이(가) 통합되어 있다고 가정한다$$.그런 다음 정수 $k{\displaystyle }$ ${\$${\displaystyle \mathrm{displaystyle}}$ $k}$의 $경우{\displaystyle }$ f${\displaystyle }$( x${\displaystyle }$) ${\displaystyle f(x)}$이(가) $k{\displaystyle }$ ${\displaystyle k}$보다 크거나 같은지 여부를 결정하는 문제$$ P가 NP-완전이다$$.다항식 시간에는 P를 풀거나 변수 개수를 $(k 2 log ⁡$ ${\displaystyle k}$)로$줄일$ 수 있다는 것이 증명된다$.$$}$ $r{\displaystyle }$ ${\displaystyle r}$을(를) $f{\displaystyle }$ ${\displaystyle f}$에 대한 위의 다선형 다항식의 정도가 되게$$$$ 한 다음 다항식 시간 내에 P를 해결하거나 변수 수를 $r{\displaystyle (k}$- ${\displaystyle 1}$) ${\displaystyle$ r$(k-1)}$로 줄일 수 있음을 증명했다$.$

참고 항목

• 부울 함수
• 2차 의사 부울 최적화

메모들

참조

• Boros, E.; Hammer, P. L. (2002). "Pseudo-Boolean Optimization". Discrete Applied Mathematics. 123 (1–3): 155–225. doi:10.1016/S0166-218X(01)00341-9.
• Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Rosamond, F.; Thomasse, S.; Yeo, A. (2011). "Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average". Proc. Of FSTTCS 2011. arXiv:1104.1135. Bibcode:2011arXiv1104.1135C.
• Ishikawa, H. (2011). "Transformation of general binary MRF minimization to the first order case". IEEE Transactions on Pattern Analysis and Machine Intelligence. 33 (6): 1234–1249. CiteSeerX 10.1.1.675.2183. doi:10.1109/tpami.2010.91. PMID 20421673. S2CID 17314555.
• Kahl, F.; Strandmark, P. (2011). Generalized Roof Duality for Pseudo-Boolean Optimization (PDF). International Conference on Computer Vision.
• O'Donnell, Ryan (2008). "Some topics in analysis of Boolean functions". ECCC TR08-055. {{cite journal}}:외부 링크 위치 journal=(도움말)
• Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). Optimizing Binary MRFs via Extended Roof Duality (PDF). Conference on Computer Vision and Pattern Recognition.
• 알렉산더 슈리버강한 다항식 시간에서 서브모듈라 함수를 최소화하는 결합 알고리즘.Journal of Combinatorial 이론, Series B, Volume 80, 2000년 11월 2일 346-355페이지.