หลักฐานธรรมชาติ
ในทฤษฎีความซับซ้อนของการคำนวณ การพิสูจน์แบบธรรมชาติ คือ การพิสูจน์ประเภทหนึ่งที่แสดงให้เห็นว่าคลาสความซับซ้อน หนึ่ง แตกต่างจากอีกคลาสหนึ่ง แม้ว่าการพิสูจน์เหล่านี้จะ "เป็นธรรมชาติ" ในบางแง่ แต่ก็สามารถแสดงให้เห็นได้ (โดยสมมติว่ามีความเชื่อกันอย่างแพร่หลายเกี่ยวกับการมีอยู่ของฟังก์ชันสุ่มเทียม ) ว่าไม่มีการพิสูจน์ใด ๆ ที่สามารถนำมาใช้แก้ปัญหา P เทียบกับ NP ได้ เลย
ภาพรวม
แนวคิดเรื่องการพิสูจน์โดยธรรมชาติได้รับการแนะนำโดยAlexander RazborovและSteven Rudichในบทความ "การพิสูจน์โดยธรรมชาติ" ซึ่งนำเสนอครั้งแรกในปี 1994 และตีพิมพ์ในภายหลังในปี 1997 ซึ่งทำให้พวกเขาได้รับรางวัล Gödel Prize ประจำ ปี 2007 [ 1 ]
โดยเฉพาะอย่างยิ่ง การพิสูจน์ตามธรรมชาติพิสูจน์ขอบเขตล่างของความซับซ้อนของวงจรของฟังก์ชันบูลีนการพิสูจน์ตามธรรมชาติแสดงให้เห็นไม่ว่าโดยตรงหรือโดยอ้อมว่าฟังก์ชันบูลีนมีคุณสมบัติเชิงการจัดเรียงตามธรรมชาติ บางอย่าง ภายใต้สมมติฐานที่ว่าฟังก์ชันสุ่มเทียมมีอยู่จริงด้วย "ความยากแบบเอกซ์โพเนนเชียล" ตามที่ระบุไว้ในทฤษฎีบทหลักของพวกเขา Razborov และ Rudich แสดงให้เห็นว่าการพิสูจน์เหล่านี้ไม่สามารถแยกชั้นความซับซ้อนบางชั้นได้ โดยเฉพาะอย่างยิ่ง สมมติว่าฟังก์ชันสุ่มเทียมมีอยู่จริง การพิสูจน์เหล่านี้ไม่สามารถแยกชั้นความซับซ้อน P และ NP ได้[ 2 ]
ตัวอย่างเช่น บทความของพวกเขาระบุว่า:
- [...] ลองพิจารณากลยุทธ์การพิสูจน์ที่มักใช้กันทั่วไปในการพิสูจน์ว่า P ≠ NP:
- กำหนดแนวคิดทางคณิตศาสตร์บางอย่างเกี่ยวกับ "ความคลาดเคลื่อน" หรือ "การกระจาย" หรือ "ความแปรผัน" ของค่าของฟังก์ชันบูลีน หรือของรูปทรงหลายเหลี่ยมหรือโครงสร้างอื่นที่เกี่ยวข้อง [...]
- แสดงให้เห็นโดยใช้การอ้างเหตุผลแบบอุปนัยว่าวงจรขนาดพหุนามสามารถคำนวณฟังก์ชันที่มีความคลาดเคลื่อน "ต่ำ" เท่านั้น [...]
- จากนั้นแสดงให้เห็นว่าSATหรือฟังก์ชันอื่น ๆ ใน NP มีค่าความคลาดเคลื่อน "สูง"
- ทฤษฎีบทหลักของเราในส่วนที่ 4 แสดงให้เห็นว่าไม่มีกลยุทธ์การพิสูจน์ใดๆ ที่จะประสบความสำเร็จได้เลย[ 3 ]
คุณสมบัติของฟังก์ชันบูลีนจะถูกนิยามว่าเป็นธรรมชาติก็ต่อเมื่อมันมีคุณสมบัติที่ตรงตามเงื่อนไขการสร้างและการมีขนาดใหญ่ที่กำหนดโดย Razborov และ Rudich โดยคร่าวๆ แล้ว เงื่อนไขการสร้างนั้นกำหนดว่าคุณสมบัตินั้นจะต้องสามารถตัดสินได้ในเวลาพหุนาม (หรือเกือบพหุนาม)เมื่อตารางความจริงขนาด2nของ ฟังก์ชันบูลีนที่มีอินพุต nตัวถูกป้อนเป็นอินพุต โดยที่เวลาจะเพิ่มขึ้นเรื่อยๆ ตามค่าn ที่เพิ่มขึ้น ซึ่งก็คือเวลาแบบเลขชี้กำลังเดี่ยวใน n คุณสมบัติที่เข้าใจง่ายมักจะ ตรงตามเงื่อนไขนี้ เงื่อนไขขนาดใหญ่กำหนดว่าคุณสมบัตินั้นจะต้องเป็นจริงสำหรับเศษส่วนที่ใหญ่พอสมควรของเซตของฟังก์ชันบูลีนทั้งหมด
คุณสมบัติหนึ่งจะมีประโยชน์ต่อภาษาที่มีความซับซ้อนระดับCก็ต่อเมื่อลำดับของฟังก์ชันบูลีนทุกชุดที่มีคุณสมบัตินั้นเกิดขึ้นอย่างไม่จำกัดจำนวนครั้ง สามารถนิยามภาษาที่อยู่นอกเหนือระดับC ได้ การพิสูจน์โดยธรรมชาติคือการพิสูจน์ที่แสดงให้เห็นว่าภาษาใดภาษาหนึ่งอยู่นอกเหนือระดับCและอ้างอิงถึงคุณสมบัติโดยธรรมชาติที่มีประโยชน์ต่อภาษา ที่มีความซับซ้อนระดับ C
Razborov และ Rudich ยกตัวอย่างการพิสูจน์ขอบเขตล่างหลายกรณีกับคลาสCที่เล็กกว่าP/polyซึ่งสามารถ "แปลงเป็นธรรมชาติ" ได้ กล่าวคือ แปลงเป็นการพิสูจน์ตามธรรมชาติ ตัวอย่างที่สำคัญคือการพิสูจน์ว่าปัญหาความเท่าเทียมกันไม่ได้อยู่ในคลาสAC 0พวกเขาให้หลักฐานที่ชัดเจนว่าเทคนิคที่ใช้ในการพิสูจน์เหล่านี้ไม่สามารถขยายเพื่อแสดงขอบเขตล่างที่แข็งแกร่งกว่าได้ โดยเฉพาะอย่างยิ่ง การพิสูจน์ตามธรรมชาติของ AC 0ไม่สามารถใช้ได้กับAC 0 [m ]
Razborov และ Rudich ยังได้นำเสนอการพิสูจน์แบบไม่มีเงื่อนไขของAvi Wigderson ที่ว่าการพิสูจน์ตามธรรมชาติไม่สามารถพิสูจน์ขอบเขตล่างแบบเลขชี้กำลังสำหรับ ปัญหาลอการิทึมแบบไม่ต่อเนื่อง ได้
ปัจจุบันมีความเชื่ออย่างแรงกล้าว่ากลไกของเอกสารฉบับนี้ขัดขวางการพิสูจน์ขอบเขตล่างต่อคลาสความซับซ้อนTC 0ของวงจรเกณฑ์ที่มีความลึกคงที่และขนาดพหุนาม ซึ่งเชื่อกันว่ามีขนาดเล็กกว่า P/poly แต่ยังไม่ได้รับการพิสูจน์[ 4 ]ความเชื่อนี้เป็นเพราะภายใต้สมมติฐานที่เชื่อกันอย่างกว้างขวางเกี่ยวกับความยากของการแยกตัวประกอบในกลุ่มเส้นโค้งวงรีบางกลุ่มมีฟังก์ชัน สุ่มเทียมที่ยากแบบเอกซ์โพเนนเชีย ลที่คำนวณได้ใน TC 0 [ 5 ]อย่างไรก็ตาม นักวิจัยบางคนเชื่อว่าข้อจำกัดของ Razborov–Rudich เป็นแนวทางที่ดีสำหรับสิ่งที่การพิสูจน์ขอบเขตล่าง "เหนือธรรมชาติ" อาจเกี่ยวข้อง เช่น คุณสมบัติที่ยากหรือสมบูรณ์สำหรับพื้นที่เอกซ์โพเนนเชียล[ 6 ]
หมายเหตุ
- ↑ "รางวัล Gödel ของ ACM-SIGACT ปี 2007" . เก็บถาวรจากต้นฉบับเมื่อ 2016-03-03 . เรียกดูเมื่อ2014-08-11 .
- ↑ AA Razborov และ S. Rudich (1997). "การพิสูจน์ตามธรรมชาติ"วารสารวิทยาการคอมพิวเตอร์และระบบ 55 : 24– 35. doi : 10.1006 /jcss.1997.1494 .( ร่าง )
- ↑ราซโบรอฟ+รูดิช (1997), เหลือหน้า 26
- ↑ "Complexity Zoo:T - Complexity Zoo "
- ↑ Naor, Moni; Reingold, Omer (2004). "การสร้างฟังก์ชันสุ่มเทียมที่มีประสิทธิภาพโดยใช้ทฤษฎีจำนวน"วารสารACM 51 ( 2): 231– 262. doi : 10.1145/972639.972643 . S2CID 8665271 .
- ↑ K. Regan (ตุลาคม 2002). "การทำความเข้าใจแนวทาง Mulmuley-Sohoni สำหรับ P เทียบกับ NP" (PDF)วารสารของสมาคมยุโรปเพื่อวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี 78 : 86– 97 .