ปัญหาที่ยังแก้ไม่ตกในวิทยาการคอมพิวเตอร์

⁠ ⁠${\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}$

ยังมีปัญหาที่ยังแก้ไม่ตกอีกมากมายในสาขาวิทยาการคอมพิวเตอร์

ในทฤษฎีความซับซ้อนของการคำนวณ NL ( Nondeterministic Logarithmic - space) คือกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบไม่กำหนด (nondeterministic Turing machine ) โดย ใช้พื้นที่หน่วยความจำในปริมาณลอการิทึม

NLเป็นการขยายความของLซึ่งเป็นคลาสสำหรับปัญหา logspace บน เครื่องทั ว ริงแบบกำหนดได้เนื่องจากเครื่องทัวริงแบบกำหนดได้ใดๆ ก็เป็นเครื่องทัวริงแบบไม่กำหนดได้ เช่นกัน ดังนั้น เราจึงได้ว่าLบรรจุอยู่ในNL

NLสามารถกำหนดอย่างเป็นทางการได้โดยใช้พื้นที่ทรัพยากรการคำนวณแบบไม่กำหนด (หรือ NSPACE) เป็นNL = NSPACE (log n )

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

บางครั้งNLถูกเรียกว่าRLเนื่องจากนิยามเชิงความน่าจะเป็นด้านล่าง อย่างไรก็ตาม ชื่อนี้มักใช้เพื่ออ้างถึงปริภูมิ เชิงลอการิทึมแบบสุ่มซึ่งไม่เป็นที่ทราบแน่ชัดว่าเท่ากับNL

มีคำจำกัดความที่เทียบเท่ากันหลายแบบสำหรับคลาส NL

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

กล่าวโดยละเอียด ภาษาหนึ่งจะเป็นภาษาธรรมชาติ (NL) ก็ต่อเมื่อมีเครื่องจักรสถานะใหม่ (NTM) อยู่จริงซึ่งทำให้ ${\displaystyle L}$${\displaystyle M}$

• ${\displaystyle M}$ทำงานบน logspace
• ${\displaystyle M}$หยุดเสมอ

• ถ้าเป็นเช่นนั้น จะมีร่องรอยการคำนวณอย่างน้อยหนึ่งรายการที่ส่งผลให้เครื่องหยุดทำงานในสถานะที่ยอมรับได้${\displaystyle x\in L}$${\displaystyle M(x)}$
• ถ้าเป็นเช่นนั้น ร่องรอยการคำนวณทั้งหมดของผลลัพธ์จะทำให้เครื่องหยุดทำงานในสถานะที่ไม่ยอมรับ${\displaystyle x\not \in L}$${\displaystyle M(x)}$

สมมติว่าCคือกลุ่มความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้ในปริภูมิเชิงลอการิทึมด้วยเครื่องจักรทัวริงเชิงความน่าจะเป็นที่ไม่ยอมรับคำตอบที่ผิดพลาดเลย แต่สามารถปฏิเสธคำตอบที่ผิดพลาดได้น้อยกว่า 1/3 ของเวลา ซึ่งเรียกว่าข้อผิดพลาดด้านเดียวค่าคงที่ 1/3 เป็นค่าใดๆ ก็ได้x ใดๆ ที่มี 0 ≤ x < 1/2 ก็เพียงพอแล้ว

ปรากฏว่าC = NLโปรดสังเกตว่าCต่างจากL ซึ่งเป็นคู่ขนานเชิงกำหนด ไม่ได้จำกัดอยู่แค่เวลาพหุนาม เพราะถึงแม้จะมีจำนวนการกำหนดค่าเป็นพหุนาม แต่ ก็สามารถใช้ความสุ่มเพื่อหลุดพ้นจากวงวนอนันต์ได้ หากเราจำกัดมันไว้ที่เวลาพหุนาม เราจะได้คลาสRLซึ่งบรรจุอยู่ใน แต่ไม่เป็นที่รู้จักหรือเชื่อว่าเท่ากับNL

มีอัลกอริทึมง่ายๆ ที่พิสูจน์ได้ว่าC = NLเห็นได้ชัดว่าCอยู่ในNLเนื่องจาก:

• หากสตริงนั้นไม่อยู่ในภาษาที่กำหนด ทั้งสองระบบจะปฏิเสธการประมวลผลในทุกเส้นทาง
• ถ้าสตริงนั้นอยู่ในภาษาดังกล่าว อัลกอริทึม ภาษาธรรมชาติจะยอมรับอย่างน้อยหนึ่งเส้นทางการคำนวณ และ อัลกอริทึมภาษา ซีจะยอมรับอย่างน้อยสองในสามของเส้นทางการคำนวณทั้งหมด

เพื่อแสดงว่าNLอยู่ในCเราเพียงแค่เลือก อัลกอริทึม NLและเลือกเส้นทางการคำนวณแบบสุ่มที่มีความยาวnแล้วดำเนินการซ้ำ 2n ^{ครั้ง}เนื่องจากไม่มีเส้นทางการคำนวณใดที่มีความยาวเกินnและเนื่องจากมีเส้นทางการคำนวณทั้งหมด 2n ^{เส้นทาง}เราจึงมีโอกาสสูงที่จะพบเส้นทางที่ยอมรับได้ (โดยมีขอบเขตล่างเป็นค่าคงที่)

ปัญหาเดียวคือเราไม่มีพื้นที่ในหน่วยความจำแบบลอการิทึมสำหรับตัวนับแบบไบนารีที่นับได้ถึง 2n ^{เพื่อ}แก้ปัญหานี้ เราจึงแทนที่ด้วย ตัวนับ แบบสุ่มซึ่งจะโยน เหรียญ nเหรียญ และหยุดหรือปฏิเสธหากเหรียญทั้งหมดออกหัว เนื่องจากเหตุการณ์นี้มีโอกาสเกิดขึ้น 2 ^{− n}เราจึงคาดว่าจะใช้ เวลาเฉลี่ย ²ⁿขั้นตอนก่อนที่จะหยุด ตัวนับนี้เพียงแค่ต้องเก็บผลรวมของจำนวนหัวที่ออกติดต่อกัน ซึ่งสามารถนับได้ในหน่วยความจำแบบลอการิทึม

เนื่องจากทฤษฎีบท Immerman–Szelepcsényiซึ่งระบุว่า NL ปิดภายใต้ส่วนเติมเต็ม ข้อผิดพลาดด้านเดียวในการคำนวณเชิงความน่าจะเป็นเหล่านี้จึงสามารถแทนที่ด้วยข้อผิดพลาดด้านศูนย์ได้ กล่าวคือ ปัญหาเหล่านี้สามารถแก้ไขได้โดยเครื่องจักรทัวริงเชิงความน่าจะเป็นที่ใช้พื้นที่ลอการิทึมและไม่ก่อให้เกิดข้อผิดพลาดเลย คลาสความซับซ้อนที่สอดคล้องกันซึ่งกำหนดให้เครื่องจักรใช้เวลาพหุนามเท่านั้นเรียกว่า ZPLP

ดังนั้น เมื่อเราพิจารณาเฉพาะเรื่องอวกาศ ดูเหมือนว่าการสุ่มและการไม่แน่นอนจะมีอิทธิพลเท่าเทียมกัน

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

ภาษาอยู่ในNLก็ต่อเมื่อ^{[ 1 ] : นิยาม 4.19} ${\displaystyle L}$

• มีฟังก์ชันพหุนามอยู่ฟังก์ชันหนึ่ง${\displaystyle p}$
• มีตัวตรวจสอบอยู่${\displaystyle TM}$
• สำหรับค่าใดๆ ก็ตามก็ต่อเมื่อมีใบรับรองที่มีความยาวอยู่จริงโดยที่${\displaystyle x}$${\displaystyle x\in L}$${\displaystyle u}$${\displaystyle |u|\leq p(|x|)}$${\displaystyle TM(x,u)=1}$

กล่าวโดยสรุป หมายความว่า ถ้าประโยคใดอยู่ในภาษานั้น ก็จะมีบทพิสูจน์ที่มีความยาวเป็นพหุนามที่พิสูจน์ได้ว่าประโยคนั้นอยู่ในภาษานั้น แต่ไม่ได้กล่าวถึงกรณีที่ประโยคนั้นไม่ได้ อยู่ ในภาษานั้น อย่างไรก็ตาม จากทฤษฎีบท Immerman–Szelepcsényi ชัดเจนว่ามีตัวตรวจสอบบางตัวที่สามารถตรวจสอบได้ทั้งสองกรณีคือ และ${\displaystyle x\in L}$${\displaystyle x\not \in L}$

โปรดทราบว่าเงื่อนไขการอ่านครั้งเดียวเป็นสิ่งจำเป็น หากตัวตรวจสอบสามารถอ่านไปข้างหน้าและข้างหลังได้ จะทำให้คลาสขยายไปเป็นคลาสNP ^{[ 1 ] : แบบฝึกหัด 4.7}

Cem Sayและ Abuzer Yakaryılmaz ได้พิสูจน์แล้วว่าเครื่องจักรทัวริงแบบลอการิทึมเชิงกำหนดในข้อความข้างต้นสามารถแทนที่ด้วยเครื่องจักรทัวริงแบบความน่าจะเป็นที่มีขอบเขตข้อผิดพลาดและมีพื้นที่คงที่ซึ่งอนุญาตให้ใช้บิตสุ่มจำนวนคงที่เท่านั้น^{[ 2 ]}

ในทฤษฎีความซับซ้อนเชิงพรรณนาภาษาธรรมชาติ (NL)ถูกนิยามว่าเป็นภาษาที่สามารถแสดงออกมาได้ในตรรกะลำดับที่หนึ่ง โดยมี ตัวดำเนินการ ปิดแบบถ่ายทอดเพิ่มเติม

คลาส NL ปิดภายใต้การดำเนินการเติมเต็ม การรวมกัน และดังนั้นจึงปิดภายใต้การดำเนินการตัดกันการต่อกันและKleene starด้วย

ปัญหาจะเรียกว่าNL-complete ก็ต่อเมื่อปัญหานั้นเป็นภาษา NLและปัญหาใดๆ ในภาษา NLสามารถลดรูปได้ในพื้นที่ลอการิทึมไปยังปัญหานั้น

ปัญหาที่ทราบกันว่า สมบูรณ์แบบ NLรวมถึงการเชื่อมต่อ STและความสามารถในการทำให้พอใจ 2ระดับ

การเชื่อมต่อแบบ STถามถึงโหนดSและTในกราฟแบบมีทิศทางว่าTสามารถเข้าถึงได้จากS หรือ ไม่

2-satisfiabilityถามว่า เมื่อกำหนด สูตร เชิงประพจน์ซึ่งแต่ละอนุประโยคเป็นการเชื่อมแบบ "หรือ " ของตัวแปรสองตัว จะมีการกำหนดค่าตัวแปรใดที่ทำให้สูตรนั้นเป็นจริงหรือไม่ ตัวอย่างหนึ่งคือ (โดยที่บ่งชี้ว่าไม่ใช่ ) อาจเป็นดังนี้: ${\displaystyle \neg }$

${\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}$

เป็นที่ทราบกันว่าNLบรรจุอยู่ในPเนื่องจากมีอัลกอริธึมแบบพหุนามสำหรับ2-satisfiabilityแต่ยังไม่ทราบแน่ชัดว่าNL = PหรือL = NLเป็นที่ทราบกันว่าNL = co-NLโดยที่co-NLคือกลุ่มของภาษาที่มีส่วนเติมเต็มอยู่ในNLผลลัพธ์นี้ ( ทฤษฎีบท Immerman–Szelepcsényi ) ถูกค้นพบโดยอิสระโดย Neil ImmermanและRóbert Szelepcsényiในปี 1987 พวกเขาได้รับรางวัล Gödel Prize ในปี 1995 จากผลงานนี้

ในแง่ของความซับซ้อนของวงจรNLสามารถจัดอยู่ใน ลำดับชั้น NCได้ ตามที่ Papadimitriou 1994 ทฤษฎีบท 16.1 ระบุไว้ว่า:

${\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}$.

กล่าว โดยละเอียดNLอยู่ในAC ¹เป็นที่ทราบกันว่าNLเท่ากับZPLซึ่งเป็นกลุ่มของปัญหาที่สามารถแก้ไขได้ด้วยอัลกอริทึมแบบสุ่มในพื้นที่ลอการิทึมและเวลาที่ไม่จำกัด โดยไม่มีข้อผิดพลาด อย่างไรก็ตาม ยังไม่เป็นที่ทราบหรือเชื่อว่า NL เท่ากับRLPหรือZPLP ซึ่งเป็นข้อจำกัดของ RLและZPLในเวลาพหุนาม ซึ่งผู้เขียนบาง คน เรียกกันว่าRLและZPL

เราสามารถเชื่อมโยงNLกับพื้นที่เชิงกำหนดได้โดยใช้ทฤษฎีบทของ Savitchซึ่งบอกเราว่าอัลกอริทึมที่ไม่กำหนดใดๆ ก็สามารถจำลองได้โดยเครื่องจักรเชิงกำหนดโดยใช้พื้นที่เพิ่มขึ้นอย่างมากที่สุดเพียงกำลังสอง จากทฤษฎีบทของ Savitch เราจึงได้โดยตรงว่า:

${\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{เทียบเท่า, }}{\mathsf {NL\subseteq L}}^{2}.}$

นี่คือการรวมพื้นที่เชิงกำหนดที่แข็งแกร่งที่สุดเท่าที่ทราบในปี 1994 (Papadimitriou 1994 ปัญหา 16.4.10 "พื้นที่สมมาตร") เนื่องจากคลาสพื้นที่ขนาดใหญ่ไม่ได้รับผลกระทบจากการเพิ่มขึ้นแบบกำลังสอง จึงทราบกันว่าคลาสที่ไม่กำหนดและคลาสที่กำหนดนั้นเท่ากัน ตัวอย่างเช่น เรามี PSPACE = NPSPACE