อะไรคือผลที่ตามมาของการบอกว่าเครื่องทัวริงที่ไม่สามารถกำหนดได้สามารถแก้ NP ในเวลาพหุนามได้

ทุกวันนี้ฉันได้ศึกษาเกี่ยวกับปัญหา NP ความซับซ้อนในการคำนวณและทฤษฎี ฉันเชื่อว่าในที่สุดฉันก็เข้าใจแนวคิดของ Turing Machine แล้ว แต่ฉันมีข้อสงสัยอยู่สองสามข้อ

ฉันยอมรับได้ว่าเครื่องทัวริงที่ไม่ได้กำหนดไว้มีหลายทางเลือกในสิ่งที่ต้องทำเพื่ออ่านสถานะและสัญลักษณ์ที่กำหนดและจะเลือกตัวเลือกที่ดีที่สุดเสมอตามที่ระบุไว้ในวิกิพีเดีย

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

สิ่งที่ฉันไม่เข้าใจก็คือ เนื่องจากนี่คือเครื่องจักรจินตภาพ เราได้อะไรจากการบอกว่ามันสามารถแก้ปัญหา NP ในเวลาพหุนามได้ ฉันหมายถึง ฉันสามารถตั้งทฤษฎีเกี่ยวกับเครื่องจักรเวทย์มนตร์ที่แก้ปัญหา NP ใน O(1) ได้ ฉันจะได้อะไรจากสิ่งนั้นถ้ามันไม่เคยมีอยู่จริง?

ขอบคุณล่วงหน้า.


complexity-theory theory turing-machines
person Clash    schedule 14.09.2010    source แหล่งที่มา
comment
นั่นเป็นความคิดเก่า เรียกว่าเครื่องออราเคิล   -  person Yuval Adam    schedule 15.09.2010

คำตอบ (6)


arrow_upward
15
arrow_downward

เครื่องจักรทัวริงที่ไม่สามารถกำหนดได้นั้นเป็นแนวคิดที่เข้าใจยาก ลองใช้มุมมองอื่นๆ:

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

  2. แทนที่จะคาดเดาหรือแยกประเด็นใดๆ ให้นึกถึงบุคคลหนึ่งที่พยายามโน้มน้าวอีกคนหนึ่งว่าเหตุการณ์นั้นควรได้รับการยอมรับ คนแรกจะจัดเตรียมชุดตัวเลือกที่จะทำโดยเครื่องทัวริงที่ไม่สามารถกำหนดได้ และคนที่สองจะตรวจสอบว่าเครื่องยอมรับอินพุตด้วยตัวเลือกเหล่านั้นหรือไม่ ถ้าเป็นเช่นนั้น บุคคลที่สองก็จะเชื่อ; หากไม่เป็นเช่นนั้น แสดงว่าคนแรกล้มเหลว (ซึ่งอาจเป็นเพราะกรณีนั้นไม่สามารถยอมรับได้ด้วยลำดับตัวเลือกใดๆ หรือเพราะคนแรกเลือกลำดับตัวเลือกที่ไม่ดี)

  3. #P4#
    #P5#
    #P6#
    #P7#
    #P8#
    #P9#
    #P10#

คุณยังกล่าวว่า

ฉันยังสามารถตั้งทฤษฎีเกี่ยวกับเครื่องจักรเวทย์มนตร์ที่แก้ปัญหา NP ใน O(1) ได้

ใช่คุณสามารถ. สิ่งเหล่านี้เรียกว่า oracle machines (ไม่เกี่ยวข้องกับ DBMS) และพวกมันให้ผลลัพธ์ที่น่าสนใจในทฤษฎีความซับซ้อน . ตัวอย่างเช่น ทฤษฎีบท BakerGillSolovay ระบุว่ามีออราเคิล A และ B สำหรับเครื่องจักรทัวริงที่สามารถเข้าถึง A, P=NP แต่สำหรับเครื่องจักรทัวริงที่สามารถเข้าถึง B, PNP (A เป็นออราเคิลที่ทรงพลังมากซึ่งทำให้การไม่กำหนดระดับไม่เกี่ยวข้อง คำจำกัดความของ B นั้นซับซ้อนเล็กน้อยและเกี่ยวข้องกับเคล็ดลับการทำให้เป็นแนวทแยง) นี่เป็นผลลัพธ์เมตาดาต้าประเภทหนึ่ง: การพิสูจน์ใด ๆ ในการแก้ไขคำถาม P กับ NP จะต้องละเอียดอ่อน เพียงพอกับคำจำกัดความของเครื่องทัวริงที่จะล้มเหลวเมื่อคุณเพิ่มออราเคิลบางประเภท

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

person Jouni K. Seppänen    schedule 03.10.2010
comment
+1. ฉันไม่เคยได้ยินเกี่ยวกับทฤษฎีบทของออราเคิลมาก่อน มันฟังดูดีมาก - person Edmund; 03.10.2010

arrow_upward
4
arrow_downward

สิ่งที่คุณได้รับจากสิ่งนั้นก็คือ คุณสามารถพิสูจน์ได้ว่าปัญหาอยู่ใน NP โดยการพิสูจน์ว่า NTM สามารถแก้ไขได้ในเวลาพหุนาม

กล่าวอีกนัยหนึ่ง คุณสามารถใช้ NTM เพื่อค้นหาว่าปัญหาที่กำหนดอยู่ใน NP หรือไม่

person sepp2k    schedule 14.09.2010
comment
คุณช่วยอธิบายรายละเอียดเกี่ยวกับเรื่องนั้นหน่อยได้ไหม? ฉันจะพิสูจน์อะไรแบบนั้นโดยใช้ NTM ได้อย่างไร - person Clash; 15.09.2010
comment
@Clash: คุณสร้าง NTM ซึ่งแก้ปัญหาได้ จากนั้นคุณพิสูจน์ว่ามันถูกต้องและมันรันในเวลาพหุนาม - person sepp2k; 15.09.2010
comment
ช่วยลงตัวอย่างลิงค์ศึกษาเรื่องดังกล่าวหน่อยได้ไหมครับ? ฉันหลงทางไปหมดแล้วว่าจะทำยังไง ฉันไม่คุ้นเคยกับการคิดแบบไม่มีกำหนด ขอบคุณ! - person Clash; 15.09.2010
comment
@Clash: ตัวอย่างเช่น คุณสามารถค้นหาได้ว่ากราฟมีไตรรงค์หรือไม่โดยการเดาแบบไม่กำหนด สำหรับ |V| รอบแรก คุณจะต้องกำหนดสีให้กับจุดยอด แล้วตรวจสอบว่าสีของคุณถูกต้องหรือไม่ ดูปัญหา NP-complete สำหรับตัวอย่างเพิ่มเติม - person sdcvvc; 15.09.2010
comment
ขอบคุณ sdwc จะลองดู! - person Clash; 15.09.2010

arrow_upward
1
arrow_downward

ตามคำจำกัดความ NP ย่อมาจากเวลาพหุนามที่ไม่สามารถกำหนดได้ ซึ่งสามารถค้นหาได้ใน Wikipedia< /ก>.

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

ดังนั้น การบอกว่า NTM สามารถ แก้ปัญหาในเวลาพหุนามได้อย่างมีประสิทธิภาพหมายความว่าปัญหานั้นอยู่ใน NP สิ่งนี้เทียบเท่ากับคำจำกัดความของปัญหาระดับ NP อีกครั้ง

person Arc    schedule 14.09.2010
comment
ขอบคุณที่ชี้แจงแต่คุณยังไม่ตอบคำถามผมเลย...ถ้าทายถูกแบบนี้ไม่มีจะมีประโยชน์อะไร...ก็เหมือนกับบอกว่า เฮ้ ถ้าผมรู้ผลลอตเตอรี่ได้ก่อนหน้านั้น บังเอิญฉันจะรวย NTM จะต้องมีประโยชน์อย่างอื่น นี่คือสิ่งที่ฉันไม่เข้าใจ - person Clash; 15.09.2010
comment
หวังว่าคอมพิวเตอร์ควอนตัม (มีข้อจำกัดบางประการ) สามารถทดสอบเส้นทางการแก้ปัญหาที่เป็นไปได้ทั้งหมดพร้อมกันได้ ดังนั้นจึงมีพฤติกรรมเหมือน NTM ที่โชคดีที่สุดที่เป็นไปได้ คอมพิวเตอร์ควอนตัมคำนวณด้วย คิวบิต โดยที่ชุดคิวบิตใดๆ แสดงถึงชุดของการรวมกันที่เป็นไปได้ทั้งหมดของบิตทั่วไปที่มีจำนวนเท่ากัน (การซ้อนทับ) (ปีเตอร์) อัลกอริทึมของ Shor สำหรับการแยกตัวประกอบตัวเลข / การถอดรหัสการเข้ารหัส RSA ใช้ประโยชน์จากสิ่งนี้ - person Arc; 15.09.2010
comment
ส่วนที่ยากสำหรับคอมพิวเตอร์ควอนตัมคือการปกป้องการซ้อนทับจากการแยกส่วน (โดยที่ qubit เปลี่ยนเป็นบิตทั่วไปโดยการโต้ตอบทางกายภาพกับโลก) และแยกวิธีแก้ปัญหาที่ถูกต้องออกมาในท้ายที่สุดด้วยการแยกส่วน - person Arc; 15.09.2010

arrow_upward
0
arrow_downward

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

ปัญหา NP เป็นปัญหาระดับพิเศษ และ NTM เป็นเพียงเครื่องมือในการตรวจสอบว่าปัญหาที่ระบุอยู่ในชั้นเรียนหรือไม่

โปรดทราบว่า NTM ไม่ใช่เครื่องจักรเฉพาะ แต่เป็นเครื่องจักรทั้งประเภทที่มีกฎเกณฑ์ที่กำหนดไว้อย่างชัดเจนว่าอะไรทำได้และไม่สามารถทำได้ ในการใช้เครื่องจักร "มหัศจรรย์" คุณต้องกำหนดพวกมันและแสดงว่าพวกมันสอดคล้องกับระดับความซับซ้อนของปัญหาใด

ดู http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes สำหรับข้อมูลเพิ่มเติม ข้อมูล.

person DanJ    schedule 14.09.2010
comment
หาก NP สามารถกำหนดได้ว่าเป็นปัญหาที่สามารถตรวจสอบได้ใน polytime ด้วย TM เหตุใดฉันจึงต้องมี NTM ซึ่งไม่มีอยู่ด้วยซ้ำ ขอบคุณ - person Clash; 15.09.2010
comment
การตรวจสอบความถูกต้องของสารละลายในโพลีไทม์ด้วย TM เทียบเท่ากับการแก้ปัญหาในโพลีไทม์ด้วย NTM en.wikipedia.org/wiki/NP_(complexity)#Verifier-based_definition (ดูความละเอียดของเครื่อง) - person DanJ; 15.09.2010
comment
บางครั้งมันง่ายกว่าที่จะเกิดขึ้นกับ NTM มากกว่า TM แต่เพื่อที่จะพิสูจน์ว่าปัญหาคือ NP ทั้งสองวิธีแก้ปัญหานั้นใช้ได้ - person DanJ; 15.09.2010

arrow_upward
-1
arrow_downward

จากวิกิพีเดียภาษาฮีบรู - "NTM เป็นเครื่องมือในการคิดเป็นหลัก และเป็นไปไม่ได้เลยที่จะนำเครื่องจักรดังกล่าวไปใช้จริง" คุณสามารถแทนที่คำว่า "NTM" ด้วย "อัลกอริทึมที่พยายามทุกขั้นตอนที่เป็นไปได้ในทุกขั้นตอน" หรือ "อัลกอริทึมที่ทุกขั้นตอนจะเลือกขั้นตอนต่อไปที่ดีที่สุดเท่าที่จะเป็นไปได้".. และฉันคิดว่าคุณเข้าใจส่วนที่เหลือ NTM อยู่ที่นี่เพื่อช่วยให้เราเห็นภาพอัลกอริทึมดังกล่าวเท่านั้น คุณสามารถดูที่นี่ ว่ามันจะช่วยให้คุณเห็นภาพได้อย่างไร (ตามคำตอบของ Pascal Cuoq)

person Oren A    schedule 14.09.2010
comment
อัลกอริธึมที่ทุกขั้นตอนสามารถเลือกได้จากหลายขั้นตอนที่เป็นไปได้ อะไรก็ได้ 'เลือก' อะไรก็ได้ NTM เป็นเพียงผู้โชคดีที่สามารถเลือกเส้นทางที่ถูกต้องในแต่ละขั้นตอน - person OTZ; 15.09.2010
comment
@OTZ: คุณสามารถคิดราวกับว่ามันพยายามทำทุกวิถีทาง (คลิกลิงก์ที่ฉันให้ไว้) คำจำกัดความทั้งสองมีค่าเท่ากัน แต่คุณพูดถูก ถ้อยคำต้นฉบับไม่ดี เปลี่ยนมันแล้ว - person Oren A; 15.09.2010

arrow_upward
-1
arrow_downward

สิ่งที่เราได้รับคือ หาก เรามีพลังเวทย์มนตร์ในการเดาขั้นตอนที่ถูกต้อง ซึ่งจะกลายเป็นถูกต้องเสมอ เราสามารถแก้ไขปัญหา NPC ได้ใน POLYTIME แน่นอนว่าเราไม่สามารถ "เดา" ขั้นตอนที่ถูกต้องได้เสมอไป มันจึงเป็นจินตนาการ แต่เช่นเดียวกับที่ตัวเลขจินตภาพใช้ได้กับปัญหาในโลกแห่งความเป็นจริง ผลที่ตามมาก็มีประโยชน์ในทางทฤษฎีเช่นกัน

ด้านบวกประการหนึ่งของการปรับเปลี่ยนปัญหาเดิมด้วยวิธีนี้ก็คือ เราสามารถจัดการปัญหาเหล่านั้นได้จากมุมที่ต่างกัน ในขอบเขตทางทฤษฎี เป็นสิ่งที่ดีเพราะเรามี (1) แนวทางที่เราสามารถทำได้ (จึงมีเอกสารมากขึ้น) และ (2) เครื่องมือที่เราสามารถใช้ได้มากขึ้นหากสามารถนำมาใช้ในสาขาอื่นๆ ได้

person OTZ    schedule 14.09.2010
comment
ฉันใช้ตัวเลขจินตภาพตลอดเวลาในงานวิศวกรรมไฟฟ้า ซึ่งมีประโยชน์จริงและมีข้อดี ในทางกลับกัน ฉันไม่เห็นข้อดีใดๆ เลยของการบอกว่าเป็นสิ่งที่สามารถแก้ไขได้อย่างน่าอัศจรรย์ในโพลีไทม์ สิ่งที่ฉันกำลังมองหาคือปัญหาในโลกแห่งความเป็นจริงที่ NTM สามารถช่วยได้ ขอบคุณ @DanJ เขากำลังพูดถึง NTM ดังนั้นจึงแก้ไขได้ใน polytime - person Clash; 15.09.2010
comment
@Clash เราไม่สามารถนำ NTM ไปใช้กับปัญหาในโลกแห่งความเป็นจริงได้ เนื่องจากเป็นไปไม่ได้ที่จะสร้างปัญหาขึ้นมาตั้งแต่แรก เพื่อประโยชน์ประการหนึ่ง โปรดอ่านย่อหน้าที่สองที่ฉันเพิ่งเพิ่มเข้าไป - person OTZ; 15.09.2010
comment
@DanJ มันคือ NPC ทัศนคติของคุณเป็นยังไงบ้าง - person OTZ; 15.09.2010
comment
ไม่มีจำนวนจินตภาพ แต่เรายังคงใช้มันในหลาย ๆ สถานการณ์ ฉันสนใจในกรณีที่ NTM มีประโยชน์สำหรับทุกสิ่ง ฉันคิดว่าในที่สุดฉันก็เข้าใจแล้วว่า NTM มีประโยชน์ในการพิสูจน์ว่าปัญหาบางอย่างคือ NP ในขณะที่การใช้ TM ที่กำหนดขึ้นเพื่อพิสูจน์สิ่งนั้นจะยากกว่า สิ่งที่ฉันต้องการตอนนี้คือตัวอย่างว่าฉันจะพิสูจน์สิ่งนั้นด้วย เอ็นทีเอ็ม. คุณนึกถึงสิ่งใดหรือคุณรู้ลิงก์ใด ๆ ไปยังสิ่งนั้นหรือไม่? ขอบคุณ! - person Clash; 15.09.2010