ในทฤษฎีความซับซ้อนของการคำนวณ SNP (จากStrict NP ) คือกลุ่มความซับซ้อนที่มีกลุ่มย่อยจำกัดของNPโดยอาศัยลักษณะเชิงตรรกะในแง่ของ คุณสมบัติ ทางทฤษฎีกราฟซึ่งเป็นพื้นฐานสำหรับการกำหนดกลุ่มMaxSNPของปัญหาการหาค่าเหมาะสมที่สุด

นิยามของมันคือ กลุ่มของปัญหาที่เป็นคุณสมบัติของโครงสร้างเชิงสัมพันธ์ (เช่นกราฟ ) ซึ่งสามารถแสดงได้ด้วย สูตร ตรรกะลำดับที่สองในรูปแบบต่อไปนี้:

${\displaystyle \exists S_{1}\dots \exists S_{\ell }\,\forall v_{1}\dots \forall v_{m}\,\phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})}$

โดยที่ความสัมพันธ์ของโครงสร้าง (เช่น ความสัมพันธ์ประชิดสำหรับกราฟ) คือความสัมพันธ์ที่ไม่ทราบ (เซตของทูเปิลของจุดยอด) และคือสูตรที่ไม่มีตัวบ่งปริมาณ: การรวมกันแบบบูลีนใดๆ ของความสัมพันธ์^{[ 1 ]}นั่นคือ อนุญาตเฉพาะการบ่งปริมาณลำดับที่สองแบบมีอยู่ (เหนือความสัมพันธ์) และอนุญาตเฉพาะการบ่งปริมาณลำดับแรกแบบสากล (เหนือจุดยอด) เท่านั้น หากอนุญาตการบ่งปริมาณแบบมีอยู่เหนือจุดยอดด้วย ระดับความซับซ้อนที่ได้จะเท่ากับ NP (กล่าวให้แม่นยำยิ่งขึ้นคือ ระดับของคุณสมบัติของโครงสร้างเชิงสัมพันธ์ที่อยู่ใน NP) ซึ่งเป็นข้อเท็จจริงที่รู้จักกันในชื่อทฤษฎีบทของเฟกิน ${\displaystyle R_{1},\dots ,R_{k}}$${\displaystyle S_{1},\dots ,S_{\ell }}$${\displaystyle \phi }$

ตัวอย่างเช่น SNP ประกอบด้วยปัญหาการระบายสี 3 สี (ปัญหาในการพิจารณาว่ากราฟที่กำหนดสามารถระบายสีด้วย 3 สีได้หรือไม่ ) เนื่องจากสามารถแสดงได้ด้วยสูตรต่อไปนี้:

${\displaystyle \exists S_{1}\exists S_{2}\exists S_{3}\,\forall u\forall v\,{\bigl (}S_{1}(u)\vee S_{2}(u)\vee S_{3}(u){\bigr )}\,\wedge \,{\bigl (}E(u,v)\,\implies \,(\neg S_{1}(u)\vee \neg S_{1}(v))\,\wedge \,\left(\neg S_{2}(u)\vee \neg S_{2}(v)\right)\,\wedge \,(\neg S_{3}(u)\vee \neg S_{3}(v)){\bigr )}}$

ในที่นี้หมายถึงความสัมพันธ์ประชิดของกราฟอินพุต ในขณะที่เซต (ความสัมพันธ์เอกภาค) สอดคล้องกับเซตของจุดยอดที่ระบายสีด้วยหนึ่งใน 3 สี ในทำนองเดียวกัน SNP ประกอบด้วย ปัญหา k -SAT: ปัญหาความพึงพอใจแบบบูลีน (SAT) ซึ่งสูตรถูกจำกัดให้อยู่ในรูปแบบปกติแบบเชื่อมโยงและมีตัวอักษรไม่เกินkตัวต่อประโยค โดยที่kเป็นค่าคงที่ ${\displaystyle E}$${\displaystyle S_{1},S_{2},S_{3}}$

นิยามที่คล้ายคลึงกันนี้พิจารณาปัญหาการหาค่าเหมาะสมที่สุดเมื่อแทนที่จะขอให้สูตรเป็นจริงสำหรับ ทูเปิล ทั้งหมดเราต้องการเพิ่มจำนวนทูเปิลที่สูตรนั้นเป็นจริงให้มากที่สุด กล่าวคือMaxSNP ₀ถูกกำหนดให้เป็นกลุ่มของปัญหาการหาค่าเหมาะสมที่สุดบนโครงสร้างเชิงสัมพันธ์ที่สามารถแสดงได้ในรูปแบบต่อไปนี้:

${\displaystyle \max \limits _{S_{1},\dots ,S_{\ell }}|\{(v_{1},\dots ,v_{m})\colon \phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})\}|}$

MaxSNPถูกกำหนดให้เป็นคลาสของปัญหาทั้งหมดที่มีการลดรูป L ( การลด รูปเชิงเส้นไม่ใช่การลดรูปลอการิทึม ) ไปยังปัญหาในMaxSNP ₀ ^{[ 2 ]} ตัวอย่างเช่นMAX-3SATเป็นปัญหาในMaxSNP ₀ : เมื่อกำหนดอินสแตนซ์ของ 3-CNF-SAT ( ปัญหาความพึงพอใจของบูลีนที่มีสูตรในรูปแบบปกติเชิงเชื่อมโยงและมีตัวอักษรไม่เกิน 3 ตัวต่อข้อความ) ให้หาการกำหนดค่าที่ตรงตามข้อความให้ได้มากที่สุดเท่าที่จะเป็นไปได้ อันที่จริง มันเป็นปัญหา ที่สมบูรณ์ ตามธรรมชาติ สำหรับMaxSNP

มีอัลกอริทึมการประมาณ ค่าอัตราส่วนคงที่ เพื่อแก้ปัญหาใดๆ ในMaxSNPดังนั้นMaxSNPจึงอยู่ในAPXซึ่งเป็นกลุ่มของปัญหาทั้งหมดที่สามารถประมาณค่าได้ภายในอัตราส่วนคงที่บางค่า อันที่จริง การปิดของMaxSNPภายใต้การลดรูป PTAS (ทั่วไปกว่าการลดรูป L เล็กน้อย) เท่ากับAPXกล่าวคือ ทุกปัญหาในAPXมีการลดรูป PTASไปยังปัญหานั้นจากปัญหาบางปัญหาในMaxSNPโดยเฉพาะอย่างยิ่ง ทุก ปัญหาที่สมบูรณ์ใน MaxSNP (ภายใต้การลดรูป L หรือภายใต้การลดรูป AP ) ก็ สมบูรณ์ ใน APX (ภายใต้การลดรูป PTAS) ด้วย และดังนั้นจึงไม่มีการลดรูป PTAS เว้นแต่P=NPอย่างไรก็ตาม การพิสูจน์เรื่องนี้อาศัยทฤษฎีบท PCPในขณะที่การพิสูจน์ความสมบูรณ์ในMaxSNPมักเป็นเรื่องง่าย

• เอพีเอ็กซ์

• สวนสัตว์แห่งความซับซ้อน : SNP
• Complexity Zoo : MaxSNP
• Complexity Zoo : MaxSNP ₀