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

ออราเคิลประเภทนี้ที่ใช้กันทั่วไปมากที่สุดคือออราเคิลความเป็นอิสระซึ่งเป็นซับรูทีนสำหรับทดสอบว่าชุดขององค์ประกอบเมทริกซ์เป็นอิสระหรือไม่ ออราเคิลประเภทอื่น ๆ อีกหลายประเภทก็ถูกนำมาใช้เช่นกัน บางส่วนได้รับการพิสูจน์แล้วว่าอ่อนแอกว่าออราเคิลความเป็นอิสระ บางส่วนแข็งแกร่งกว่า และบางส่วนเทียบเท่ากันในด้านพลังการคำนวณ^{[ 1 ]}

อัลกอริทึมจำนวนมากที่ทำการคำนวณบนแมทรอยด์ได้รับการออกแบบให้รับออราเคิลเป็นอินพุต ทำให้สามารถทำงานได้อย่างมีประสิทธิภาพโดยไม่ต้องเปลี่ยนแปลงบนแมทรอยด์หลายประเภท และไม่ต้องมีข้อสมมติเพิ่มเติมเกี่ยวกับประเภทของแมทรอยด์ที่ใช้ ตัวอย่างเช่น เมื่อมีออราเคิลความเป็นอิสระสำหรับแมทรอยด์ใดๆ ก็สามารถค้นหาฐานที่มีน้ำหนักน้อยที่สุดของแมทรอยด์ได้โดยใช้อัลกอริทึมแบบโลภที่เพิ่มองค์ประกอบลงในฐานตามลำดับน้ำหนัก โดยใช้ออราเคิลความเป็นอิสระเพื่อทดสอบว่าสามารถเพิ่มองค์ประกอบแต่ละตัวได้หรือไม่^{[ 2 ]}

ในทฤษฎีความซับซ้อนของการคำนวณโมเดลออราเคิลได้นำไปสู่ขอบเขตล่าง แบบไม่มีเงื่อนไข ที่พิสูจน์ว่าปัญหาเมทริกซ์บางอย่างไม่สามารถแก้ไขได้ในเวลาพหุนาม โดยไม่ต้องอ้างถึงสมมติฐานที่ยังไม่ได้รับการพิสูจน์ เช่น สมมติฐานที่ว่าP ≠ NPปัญหาที่แสดงให้เห็นว่ายากในลักษณะนี้ ได้แก่ การทดสอบว่าเมทริกซ์เป็นไบนารีหรือสม่ำเสมอหรือการทดสอบว่ามีไมเนอร์ คงที่บางอย่างหรือ ไม่^{[ 3 ]}

แม้ว่าผู้เขียนบางคนได้ทดลองกับการแสดงแทนด้วยคอมพิวเตอร์ของแมทรอยด์ที่แสดงรายการเซตอิสระทั้งหมดหรือเซตฐานทั้งหมดของแมทรอยด์อย่างชัดเจน^{[ 4 ]}แต่การแสดงแทนเหล่านี้ก็ไม่กระชับ : แมทรอยด์ที่มีองค์ประกอบอาจขยายออกเป็นการแสดงแทนที่ใช้พื้นที่แบบเลขชี้กำลังตามอันที่จริง จำนวนแมทรอยด์ที่แตกต่างกันบนองค์ประกอบจะเพิ่มขึ้นแบบเลขชี้กำลังสองเท่าตาม ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

${\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}$^{[ 5 ]}

ซึ่งสรุปได้ว่าการแสดงแบบชัดเจนใดๆ ที่สามารถจัดการกับ matroid ที่เป็นไปได้ทั้งหมดจะต้องใช้พื้นที่เลขชี้กำลัง^{[ 6 ]}

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

เริ่มตั้งแต่Rado (1942) “ฟังก์ชันความเป็นอิสระ” หรือ “ ฟังก์ชัน -” ได้รับการศึกษาในฐานะหนึ่งในวิธีการเทียบเท่ามากมายในการกำหนดสัจพจน์ของ matroid ฟังก์ชันความเป็นอิสระจะแมปเซตขององค์ประกอบ matroid ไปยังจำนวนถ้าเซตนั้นเป็นอิสระหรือถ้าเซตนั้นขึ้นอยู่กัน กล่าวคือ เป็นฟังก์ชันบ่งชี้ของตระกูลเซตอิสระ ซึ่งโดยพื้นฐานแล้วเหมือนกับออราเคิลความเป็นอิสระ^{[ 7 ]}${\displaystyle I}$${\displaystyle 1}$${\displaystyle 0}$

ออราเคิลของแมทรอยด์ยังเป็นส่วนหนึ่งของงานด้านอัลกอริทึมยุคแรกๆ เกี่ยวกับแมทรอยด์ด้วย ดังนั้นเอ็ดมอนด์ส (1965)ในการศึกษาปัญหาการแบ่งส่วนของแมทรอยด์ ได้ตั้งสมมติฐานว่าการเข้าถึงแมทรอยด์ที่กำหนดนั้นทำได้ผ่านซับรูทีนที่รับอินพุตเป็นเซตอิสระและองค์ประกอบและส่งคืนวงจรใน(ซึ่งจำเป็นต้องมีเพียงหนึ่งเดียวและมีองค์ประกอบนั้นอยู่ หากมี) หรือตรวจสอบว่าไม่มีวงจรดังกล่าวอยู่เอ็ดมอนด์ส (1971)ใช้ซับรูทีนที่ทดสอบว่าเซตที่กำหนดนั้นเป็นอิสระหรือไม่ (กล่าวคือ ในศัพท์สมัยใหม่เรียกว่าออราเคิลความเป็นอิสระ ) และสังเกตว่าข้อมูลที่ได้นั้นเพียงพอที่จะค้นหาฐานที่มีน้ำหนักน้อยที่สุดได้ในเวลาพหุนาม ${\displaystyle I}$${\displaystyle x}$${\displaystyle I\cup \{x\}}$${\displaystyle x}$

จากผลงานของ Korte & Hausmann (1978)และ Hausmann & Korte (1978)นักวิจัยเริ่มศึกษาออราเคิลจากมุมมองของการพิสูจน์ขอบเขตล่างของอัลกอริทึมสำหรับแมทรอยด์และโครงสร้างที่เกี่ยวข้อง บทความทั้งสองฉบับของ Hausmann และ Korte เกี่ยวข้องกับปัญหาการค้นหาเซตอิสระที่มีขนาดสูงสุด ซึ่งง่ายสำหรับแมทรอยด์ แต่ (ดังที่พวกเขาแสดงให้เห็น) ยากที่จะประมาณหรือคำนวณได้อย่างแม่นยำสำหรับระบบอิสระ ทั่วไป ที่แสดงโดยออราเคิลอิสระ งานนี้ได้จุดประกายให้เกิดบทความจำนวนมากในช่วงปลายทศวรรษ 1970 และต้นทศวรรษ 1980 ที่แสดงผลลัพธ์ความยากที่คล้ายกันสำหรับปัญหาเกี่ยวกับแมทรอยด์^{[ 8 ]}และเปรียบเทียบพลังของออราเคิลแมทรอยด์ประเภทต่างๆ^{[ 9 ]}

นับตั้งแต่นั้นมา ออราเคิลอิสระได้กลายเป็นมาตรฐานสำหรับการวิจัยส่วนใหญ่เกี่ยวกับอัลกอริธึมเมทริกซ์^{[ 10 ]}นอกจากนี้ยังมีการวิจัยอย่างต่อเนื่องเกี่ยวกับขอบเขตล่าง^{[ 11 ]}และการเปรียบเทียบออราเคิลประเภทต่างๆ^{[ 12 ]}

ได้มีการพิจารณาประเภทของออราเคิลประเภทมาทรอยด์ดังต่อไปนี้

• ออราเคิลความเป็นอิสระจะรับชุดขององค์ประกอบ matroid เป็นอินพุต และส่งคืนค่าบูลีนเป็นเอาต์พุต โดยจะเป็นค่าจริงหากชุดที่กำหนดเป็นอิสระ และเป็นค่าเท็จในกรณีอื่น^{[ 13 ]}สามารถนำไปใช้งานได้ง่ายโดยอาศัยโครงสร้างพื้นฐานที่กำหนด matroid สำหรับgraphic matroids , transversal matroids , gammoidsและ linear matroids และสำหรับ matroids ที่สร้างขึ้นจากสิ่งเหล่านี้โดยการดำเนินการมาตรฐาน เช่น ผลรวมโดยตรง^{[ 3 ]}
• ออราเคิลพื้นฐานจะรับชุดองค์ประกอบ matroid เป็นอินพุต และส่งคืนค่าบูลีนเป็นเอาต์พุต โดยจะเป็นค่า true หากชุดที่กำหนดเป็นพื้นฐาน และค่า false ในกรณีอื่น^{[ 9 ]}
• ออราเคิลวงจรจะรับชุดองค์ประกอบ matroid เป็นอินพุต และส่งคืนค่าบูลีนเป็นเอาต์พุต โดยจะเป็นค่า true หากชุดที่กำหนดเป็นวงจร และค่า false ในกรณีอื่น^{[ 9 ]}
• ตัวค้นหาวงจรของEdmonds (1965)รับข้อมูลเข้าเป็นเซตอิสระและองค์ประกอบเพิ่มเติม จากนั้นจะพิจารณาว่าผลรวมของเซตเหล่านั้นเป็นอิสระหรือไม่ หรือค้นหาวงจรในผลรวมและส่งคืนค่าดังกล่าว
• ออราเคิลอันดับจะรับชุดขององค์ประกอบ matroid เป็นอินพุต และส่งคืนค่าตัวเลข ซึ่งเป็นอันดับของชุดที่กำหนด เป็นเอาต์พุต ^{[ 9 ]}
• มีการพิจารณาออราเคิลการปิดสามประเภท ได้แก่ ประเภทที่ทดสอบว่าองค์ประกอบที่กำหนดเป็นส่วนหนึ่งของการปิดของเซตที่กำหนดหรือไม่ ประเภทที่สองที่ส่งคืนการปิดของเซต และประเภทที่สามที่ทดสอบว่าเซตที่กำหนดปิดหรือไม่ ^{[ 9 ]}
• ออราเคิลแบบครอบคลุมจะรับชุดขององค์ประกอบ matroid เป็นอินพุต และส่งคืนค่าบูลีนเป็นเอาต์พุต โดยจะเป็นค่าจริงหากชุดที่กำหนดเป็นแบบครอบคลุม (กล่าวคือมีฐานและมีอันดับเดียวกันกับ matroid ทั้งหมด) และเป็นค่าเท็จในกรณีอื่น^{[ 14 ]}
• ตัวทำนายเส้นรอบวงจะรับชุดขององค์ประกอบ matroid เป็นอินพุต และส่งคืนค่าตัวเลขเป็นเอาต์พุต ซึ่งก็คือขนาดของวงจรที่เล็กที่สุดภายในชุดนั้น (หรือถ้าชุดที่กำหนดเป็นอิสระ) ^{[ 14 ]}${\displaystyle +\infty }$
• พอร์ตออราเคิลสำหรับองค์ประกอบคงที่ของแมทรอยด์จะรับชุดขององค์ประกอบแมทรอยด์เป็นอินพุต และส่งคืนค่าบูลีนเป็นเอาต์พุต โดยจะเป็นค่าจริงหากชุดที่กำหนดมีวงจรที่รวมอยู่และเป็นค่าเท็จในกรณีอื่น^{[ 15 ]}${\displaystyle x}$${\displaystyle x}$

แม้ว่าจะมีออราเคิลหลายประเภทที่เป็นที่รู้จัก แต่การเลือกใช้ออราเคิลนั้นสามารถทำให้ง่ายขึ้นได้ เนื่องจากออราเคิลหลายประเภทมีประสิทธิภาพในการคำนวณเทียบเท่ากัน ออราเคิลจะเรียกว่าสามารถลดรูปได้แบบพหุนามไปยังออราเคิลอื่นได้หากการเรียกใช้ใดๆสามารถจำลองได้ด้วยอัลกอริทึมที่เข้าถึงแมทรอยด์โดยใช้ออราเคิลเพียงอย่างเดียวและใช้เวลาแบบพหุนามเมื่อวัดจากจำนวนองค์ประกอบของแมทรอยด์ ในแง่ของทฤษฎีความซับซ้อน นี่คือการลดรูปทัวริงออราเคิลสองตัวจะเรียกว่าเทียบเท่ากันแบบพหุนามหากพวกมันสามารถลดรูปได้แบบพหุนามซึ่งกันและกัน หากและเทียบเท่ากันแบบพหุนามแล้ว ผลลัพธ์ทุกอย่างที่พิสูจน์การมีอยู่หรือไม่มีอยู่ของอัลกอริทึมเวลาพหุนามสำหรับปัญหาแมทรอยด์โดยใช้ออราเคิลก็จะพิสูจน์สิ่งเดียวกันสำหรับออราเคิล ด้วยเช่นกัน ${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$

ตัวอย่างเช่น ออราเคิลความเป็นอิสระเทียบเท่ากับออราเคิลการค้นหาวงจรของEdmonds (1965) ในรูปแบบพหุนามหากมีออราเคิลการค้นหาวงจรอยู่ ชุดอาจถูกทดสอบความเป็นอิสระโดยใช้การเรียกออราเคิลไม่เกิน โดยเริ่มจากชุดว่างเพิ่มองค์ประกอบของชุดที่กำหนดทีละองค์ประกอบ และใช้ออราเคิลการค้นหาวงจรเพื่อทดสอบว่าการเพิ่มแต่ละครั้งยังคงรักษาความเป็นอิสระของชุดที่สร้างขึ้นมาจนถึงตอนนี้หรือไม่ ในทางกลับกัน หากมีออราเคิลความเป็นอิสระอยู่ วงจรในชุด อาจถูกค้นหาโดยใช้ การเรียกออราเคิลไม่เกิน โดยทดสอบสำหรับแต่ละองค์ประกอบ ว่าเป็นอิสระ หรือไม่ และส่งคืนองค์ประกอบที่คำตอบคือไม่ใช่ ออราเคิลความเป็นอิสระยังเทียบเท่ากับออราเคิลอันดับ ออราเคิลการแผ่ขยาย ออราเคิลการปิดสองประเภทแรก และออราเคิลพอร์ตในรูปแบบพหุนามด้วย^{[ 1 ]}${\displaystyle n}$${\displaystyle I\cup \{x\}}$${\displaystyle n}$${\displaystyle y\in I}$${\displaystyle I\setminus \{y\}\cup \{x\}}$

ออราเคิลพื้นฐาน ออราเคิลวงจร และออราเคิลที่ทดสอบว่าเซตที่กำหนดปิดหรือไม่นั้น ล้วนอ่อนแอกว่าออราเคิลความเป็นอิสระ: สามารถจำลองได้ในเวลาพหุนามโดยอัลกอริทึมที่เข้าถึงแมทรอยด์โดยใช้ออราเคิลความเป็นอิสระ แต่ในทางกลับกันทำไม่ได้ นอกจากนี้ ออราเคิลทั้งสามนี้ไม่สามารถจำลองซึ่งกันและกันได้ภายในเวลาพหุนาม ออราเคิลเส้นรอบวงแข็งแกร่งกว่าออราเคิลความเป็นอิสระในความหมายเดียวกัน^{[ 9 ]}

นอกเหนือจากการลดรูปทัวริงแบบใช้เวลาพหุนามแล้ว ยังมีการพิจารณาการลดรูปประเภทอื่นๆ อีกด้วย โดยเฉพาะอย่างยิ่งKarp, Upfal & Wigderson (1988)แสดงให้เห็นว่า ในอัลกอริทึมแบบขนานนั้นตัวทำนายอันดับและตัวทำนายความเป็นอิสระมีความแตกต่างกันอย่างมากในด้านกำลังการคำนวณ ตัวทำนายอันดับช่วยให้สามารถสร้างฐานที่มีน้ำหนักน้อยที่สุดได้โดยการสอบถามพร้อมกันของคำนำหน้าของลำดับที่เรียงแล้วขององค์ประกอบเมทริกซ์: องค์ประกอบหนึ่งๆ จะอยู่ในฐานที่เหมาะสมที่สุดก็ต่อเมื่ออันดับของคำนำหน้าของมันแตกต่างจากอันดับของคำนำหน้าก่อนหน้า ในทางตรงกันข้าม การหาฐานที่น้อยที่สุดด้วยตัวทำนายความเป็นอิสระนั้นช้ากว่ามาก: สามารถแก้ไขได้แบบกำหนดได้ในขั้นตอนเวลา และมีขอบเขตล่างแม้กระทั่งสำหรับอัลกอริทึมแบบขนานแบบสุ่ม ${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle \โอเมก้า ((n/\log n)^{1/3})}$

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

• การค้นหาฐานน้ำหนักขั้นต่ำหรือสูงสุดของเมทริกซ์ถ่วงน้ำหนักโดยใช้อัลกอริทึมโลภ^{[ 2 ]}
• การแบ่งองค์ประกอบของแมทรอยด์ออกเป็นเซตอิสระจำนวนน้อยที่สุด และการหาเซตที่ใหญ่ที่สุดที่เป็นอิสระพร้อมกันในแมทรอยด์สองตัวที่กำหนด ปัญหาหลังนี้เรียกว่าการตัดกันของแมทรอยด์และวิธีแก้ปัญหาทั้งสองมีความสัมพันธ์กันอย่างใกล้ชิด^{[ 16 ]}
• การทดสอบว่า matroid เชื่อมต่อกันหรือไม่ (ในความหมายของTutte 1966 ) สำหรับ^{[ 17 ]}${\displaystyle k}$${\displaystyle k\leq 3}$
• ^{การทดสอบ ว่า} matroid ที่กำหนดเป็นกราฟิก^{[ 18 ]}หรือปกติ^[ 19 ^]
• การค้นหาการแยกส่วนหูของ matroid ที่กำหนด ซึ่งเป็นลำดับของวงจรที่ผลรวมเป็น matroid และแต่ละวงจรยังคงเป็นวงจรหลังจากที่วงจรก่อนหน้าทั้งหมดในลำดับนั้นถูกยุบรวม การแยกส่วนดังกล่าวอาจพบได้ด้วยคุณสมบัติเพิ่มเติมที่ว่าองค์ประกอบ matroid ที่เลือกเป็นของทุกวงจร^{[ 15 ]}
• การค้นหาการแยกสาขาของเมทริกซ์ที่กำหนด เมื่อใดก็ตามที่ความกว้างของสาขาไม่เกินค่าคงที่ที่กำหนดไว้^{[ 20 ]}
• แสดงรายการฐาน แฟลต หรือวงจรทั้งหมดของแมทรอยด์ในเวลาพหุนามต่อชุดเอาต์พุต^{[ 21 ]}
• การประมาณจำนวนฐานโดยใช้แผนการประมาณแบบสุ่มที่ใช้เวลาพหุนามอย่างสมบูรณ์สำหรับเมทริกซ์ที่มีองค์ประกอบและอันดับโดยมีข้อสมมติเพิ่มเติมว่าจำนวนฐานอยู่ภายในปัจจัยพหุนามของจำนวนเซตที่มีองค์ประกอบ^{[ 22 ]}${\displaystyle n}$${\displaystyle r}$${\displaystyle r}$

สำหรับปัญหา matroid จำนวนมาก เป็นไปได้ที่จะแสดงให้เห็นว่าออราเคิลอิสระไม่ได้ให้พลังมากพอที่จะทำให้สามารถแก้ปัญหาได้ในเวลาพหุนาม แนวคิดหลักของการพิสูจน์เหล่านี้คือการค้นหา matroid สองตัวที่คำตอบของปัญหาแตกต่างกันและยากที่อัลกอริทึมจะแยกแยะได้ โดยเฉพาะอย่างยิ่ง ถ้ามีระดับความสมมาตรสูง และแตกต่างจากเฉพาะในคำตอบของการสอบถามจำนวนเล็กน้อยเท่านั้น อาจต้องใช้การสอบถามจำนวนมากสำหรับอัลกอริทึมเพื่อให้แน่ใจว่าสามารถแยกแยะอินพุตประเภทจากอินพุตที่สร้างขึ้นโดยใช้ความสมมาตรอย่างใดอย่างหนึ่งของเพื่อสลับตำแหน่ง^{[ 3 ]}${\displaystyle M}$${\displaystyle M'}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M'}$

ตัวอย่างง่ายๆ ของแนวทางนี้สามารถใช้เพื่อแสดงให้เห็นว่าการทดสอบว่าแมทรอยด์เป็นแบบเอกรูป หรือไม่นั้นเป็นเรื่องยาก เพื่อความง่ายในการอธิบาย สมมติให้เป็นจำนวนคู่ ให้เป็นแมทรอยด์เอกรูปและให้เป็นแมทรอยด์ที่สร้างขึ้นจาก โดยการทำให้ เซตฐานที่ มีสมาชิก ตัวใดตัวหนึ่งของ เป็น เซต ที่ขึ้นอยู่กันแทนที่จะเป็นเซตอิสระ เพื่อให้ขั้นตอนวิธีสามารถทดสอบได้อย่างถูกต้องว่าอินพุตเป็นแบบเอกรูปหรือไม่ ขั้นตอนวิธีนั้นจะต้องสามารถแยกแยะ ออกจากการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดของแต่เพื่อให้ขั้นตอนวิธีเชิงกำหนดทำเช่นนั้นได้ ขั้นตอนวิธีนั้นจะต้องทดสอบเซตย่อยที่มีสมาชิก ตัวทั้งหมดของสมาชิก หากพลาดเซตใดเซตหนึ่งไป ขั้นตอนวิธีนั้นอาจถูกหลอกโดยออราเคิลที่เลือกเซตเดียวกันนั้นเป็นเซตที่จะทำให้เป็นเซตที่ขึ้นอยู่กัน ดังนั้น การทดสอบว่าแมทรอยด์เป็นแบบเอกรูปหรือไม่อาจต้องใช้ ${\displaystyle n}$${\displaystyle M}$${\displaystyle U{}_{n}^{n/2}}$${\displaystyle M'}$${\displaystyle M}$${\displaystyle n/2}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle n/2}$

${\displaystyle {\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)}$

การสอบถามความเป็นอิสระสูงกว่าพหุนามมาก แม้แต่อัลกอริทึมแบบสุ่ม ก็ ต้องทำการสอบถามเกือบเท่าจำนวนครั้งเพื่อให้มั่นใจได้ว่าสามารถแยกแยะเมทริกซ์ทั้งสองนี้ได้^{[ 23 ]}

Jensen & Korte (1982)ได้วางกรอบแนวทางนี้โดยพิสูจน์ว่า เมื่อใดก็ตามที่มีเมทริกซ์สองตัวที่มีเซตขององค์ประกอบเดียวกันแต่มีคำตอบของปัญหาที่แตกต่างกัน อัลกอริทึมที่แก้ปัญหาที่กำหนดบนองค์ประกอบเหล่านั้นได้อย่างถูกต้องจะต้องใช้อย่างน้อย ${\displaystyle M}$${\displaystyle M'}$

${\displaystyle {\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}}$

คำถาม โดยที่แทนกลุ่มออโตมอร์ฟิซึมของแทนตระกูลของเซตที่มีความเป็นอิสระแตกต่างกันตั้งแต่ถึงและแทนกลุ่มย่อยของออโตมอร์ฟิซึมที่แมปไปยังตัวมันเอง ตัวอย่างเช่น กลุ่มออโตมอร์ฟิซึมของมาทรอยด์แบบเอกรูปก็คือกลุ่มสมมาตรที่มีขนาดและในปัญหาการทดสอบมาทรอยด์แบบเอกรูป มีเพียงเซตเดียวที่มี เล็กกว่า ด้วยปัจจัยเลขชี้กำลัง^{[ 24 ]}${\displaystyle \operatorname {aut} (M)}$${\displaystyle M}$${\displaystyle Q_{i}}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle \operatorname {fix} (M,Q_{i})}$${\displaystyle Q_{i}}$${\displaystyle n!}$${\displaystyle Q_{i}}$${\displaystyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}}$${\displaystyle n!}$

ปัญหาที่ได้รับการพิสูจน์แล้วว่าอัลกอริทึมออราเคิลแบบเมทริกซ์ไม่สามารถคำนวณได้ในเวลาพหุนาม ได้แก่:

• การทดสอบว่า matroid ที่กำหนดนั้นเป็นแบบสม่ำเสมอหรือไม่^{[ 23 ]}
• การทดสอบว่า matroid ที่กำหนดมี matroid คงที่เป็น minor หรือไม่ ยกเว้นในกรณีพิเศษที่เป็น uniform ที่มี rank หรือ corank ไม่เกินหนึ่ง โดยทั่วไปแล้ว ถ้าเป็นเซตจำกัดของ matroid ที่กำหนดไว้ และไม่มี matroid ที่เป็น uniform ในจะไม่สามารถทดสอบได้ในเวลาพหุนามว่า matroid ที่กำหนดมี matroid อย่างน้อยหนึ่งตัวในเป็น minor หรือ ไม่ ^{[ 25 ]}${\displaystyle H}$${\displaystyle H}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$
• การทดสอบว่า matroid ที่กำหนดเป็นไบนารี หรือไม่ สามารถแสดงแทนได้บน ฟิลด์คงที่ใด ๆหรือมีฟิลด์ที่สามารถแสดงแทนได้หรือไม่^{[ 26 ]}
• การแก้ปัญหาการจับคู่ matroid ซึ่งอินพุตคือกราฟและ matroid บนจุดยอด และเป้าหมายคือการค้นหาการจับคู่ในกราฟที่มีขนาดใหญ่ที่สุดเท่าที่จะเป็นไปได้ ภายใต้ข้อจำกัดที่ว่าจุดยอดที่จับคู่กันนั้นเป็นเซตอิสระ^{[ 27 ]}
• การทดสอบว่า matroid ที่กำหนดนั้นเป็นแบบself-dual , transversal , bipartite , Eulerianหรือorientableหรือไม่^{[ 3 ]}
• การคำนวณเส้นรอบวง (ขนาดของวงจรที่เล็กที่สุด) ขนาดของวงจรที่ใหญ่ที่สุด จำนวนวงจร จำนวนฐาน จำนวนแฟลต จำนวนแฟลตที่มีอันดับสูงสุด ขนาดของแฟลตที่ใหญ่ที่สุดพหุนาม Tutteหรือการเชื่อมต่อของ matroid ที่กำหนด^{[ 3 ]}

ในบรรดาสมบัติทั้งหมดของเมทริกซ์องค์ประกอบ เศษส่วนของสมบัติที่ไม่ต้องการเวลาเลขชี้กำลังในการทดสอบจะเข้าใกล้ศูนย์เมื่อเข้าสู่อนันต์^{[ 6 ]}${\displaystyle n}$${\displaystyle n}$

• กลุ่มกล่องดำโมเดลคล้ายออราเคิลสำหรับทฤษฎีกลุ่ม
• กราฟโดยปริยาย (Implicit graph ) โมเดลคล้ายออราเคิลสำหรับอัลกอริธึมกราฟ