ในทางคณิตศาสตร์และการหาค่าเหมาะสมที่สุดฟังก์ชันเสมือนบูลีน (pseudo-Boolean function)คือฟังก์ชันที่มีรูปแบบดังนี้

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

โดยที่B = {0, 1}คือโดเมนบูลีนและnคือจำนวนเต็มที่ ไม่เป็นลบ เรียกว่าจำนวนอาร์กิวเมนต์ของฟังก์ชัน ฟังก์ชันบูลีนจึงเป็นกรณีพิเศษที่ค่าต่างๆ ถูกจำกัดไว้ที่ 0 หรือ 1 เช่นกัน

ฟังก์ชัน pseudo-Boolean ใดๆ สามารถเขียนได้เป็น พหุนาม เชิงเส้นหลายตัวที่ ไม่ซ้ำกัน : ^{[ 1 ] [ 2 ]}

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

ระดับของฟังก์ชันเสมือนบูลีนนั้นก็คือระดับของพหุนามในการแสดงแบบนี้

ในหลายกรณี (เช่น ในการวิเคราะห์ฟูริเยร์ของฟังก์ชันเสมือนบูลีน ) ฟังก์ชันเสมือนบูลีนถูกมองว่าเป็นฟังก์ชันที่แมปไปยัง ในกรณีนี้ เราสามารถเขียน ในรูปพหุนามหลายเชิงเส้นได้อย่างไม่ซ้ำกันดังนี้: โดยที่คือสัมประสิทธิ์ฟูริเยร์ของและตามลำดับ ${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$${\displaystyle \mathbb {R} }$${\displaystyle f}$${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}$${\displaystyle {\hat {f}}(I)}$${\displaystyle f}$${\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เป็นพหุนามกำลังสอง แนวคิดที่เรียกว่าroof dualityสามารถใช้เพื่อหาขอบเขตล่างสำหรับค่าต่ำสุดได้^{[ 3 ]} Roof duality อาจให้การกำหนดค่าบางส่วนของตัวแปร ซึ่งบ่งชี้ถึงค่าบางส่วนของตัวลดค่าต่ำสุดให้กับพหุนาม วิธีการต่างๆ ในการหาขอบเขตล่างได้รับการพัฒนาขึ้น แต่ต่อมาพบว่าเทียบเท่ากับสิ่งที่เรียกว่า roof duality ในปัจจุบัน^{[ 3 ]}

ถ้าดีกรีของfมากกว่า 2 เราสามารถใช้การลดรูปเพื่อหาปัญหาเชิงกำลังสองที่เทียบเท่ากันโดยมีตัวแปรเพิ่มเติมได้เสมอ การลดรูปที่เป็นไปได้วิธีหนึ่งคือ

${\displaystyle \displaystyle -x_{1}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 _{z\in \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.}$

การลดรูปที่แตกต่างกันจะนำไปสู่ผลลัพธ์ที่แตกต่างกัน ตัวอย่างเช่นพหุนามลูกบาศก์ ต่อไปนี้ : ^{[ 4 ]}

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

เมื่อใช้การลดรูปครั้งแรกตามด้วยทฤษฎีบทคู่ของหลังคา เราจะได้ขอบล่างที่ −3 และไม่มีข้อบ่งชี้ใด ๆ เกี่ยวกับวิธีการกำหนดตัวแปรทั้งสาม เมื่อใช้การลดรูปครั้งที่สอง เราจะได้ขอบล่าง (ที่แน่น) ที่ −2 และการกำหนดค่าที่เหมาะสมที่สุดสำหรับตัวแปรแต่ละตัว (ซึ่งคือ) ${\displaystyle {(0,1,1)}}$

พิจารณาฟังก์ชัน pseudo-Boolean เป็นการแมปจากไปยัง จากนั้น สมมติว่าสัมประสิทธิ์แต่ละตัวเป็นจำนวนเต็ม แล้วสำหรับจำนวนเต็มปัญหา P ของการตัดสินใจว่ามากกว่าหรือเท่ากับเป็นปัญหา NP-complete มีการพิสูจน์ใน^{[ 5 ]}ว่าในเวลาพหุนามเราสามารถแก้ปัญหา P หรือลดจำนวนตัวแปรลงได้ ให้เป็นดีกรีของพหุนามหลายเชิงเส้นข้างต้นสำหรับจากนั้น^{[ 5 ]}พิสูจน์ว่าในเวลาพหุนามเราสามารถแก้ปัญหา P หรือลดจำนวนตัวแปรลงได้ ${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$${\displaystyle \mathbb {R} }$${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}$${\displaystyle {\hat {f}}(I)}$${\displaystyle k}$${\displaystyle f(x)}$${\displaystyle k}$${\displaystyle O(k^{2}\log k).}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r(k-1)}$

• ฟังก์ชันบูลีน
• การเพิ่มประสิทธิภาพแบบซูโดบูลีนกำลังสอง