ในทฤษฎีความซับซ้อนของการคำนวณ L (หรือที่รู้จักกันในชื่อLSPACE , LOGSPACEหรือDLOGSPACE ) คือคลาสความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบกำหนดโดยใช้พื้นที่หน่วยความจำที่เขียนได้ในปริมาณลอการิทึม[ ^{1 ] [ 2 ] ตาม}หลักการแล้ว เครื่องจักรทัวริงมีเทปสองอันอันหนึ่งเข้ารหัสอินพุตและสามารถอ่านได้เท่านั้น^{[ 3 ]} ในขณะที่อีกอันมีขนาดลอการิทึมแต่สามารถเขียนได้เช่นเดียวกับการอ่าน พื้นที่ลอการิทึมเพียงพอที่จะเก็บตัว ชี้จำนวนคงที่ไปยังอินพุต^{[ 1 ]}และแฟล็กบูลีนจำนวนลอการิทึม และอัลกอริทึม logspace พื้นฐานจำนวนมากใช้หน่วยความจำในลักษณะนี้

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

ผลลัพธ์ในปี 2004 โดยOmer Reingoldแสดงให้เห็นว่าUSTCONซึ่งเป็นปัญหาว่ามีเส้นทางระหว่างจุดยอดสองจุดในกราฟแบบไม่มีทิศทางที่กำหนดหรือไม่ นั้น อยู่ในLซึ่งแสดงให้เห็นว่าL = SLเนื่องจาก USTCON สมบูรณ์แบบSL ^{[ 5 ]}

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

Lเป็นคลาสย่อยของNLซึ่งเป็นคลาสของภาษาที่สามารถตัดสินได้ในพื้นที่ลอการิทึม บน เครื่องทัวริงแบบไม่กำหนดปัญหาในNLอาจถูกแปลงเป็นปัญหาการเข้าถึงได้ในกราฟทิศทางที่แสดงสถานะและการเปลี่ยนสถานะของเครื่องแบบไม่กำหนด และขอบเขตของพื้นที่ลอการิทึมบ่งชี้ว่ากราฟนี้มีจำนวนจุดยอดและขอบเป็นพหุนาม ซึ่งจากนั้นจึงสรุปได้ว่าNLอยู่ในคลาสความซับซ้อนPของปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามแบบกำหนด^{[ 6 ]}ดังนั้นL  ⊆  NL  ⊆  PการรวมLเข้าในPสามารถพิสูจน์ได้โดยตรงมากขึ้น: ตัวตัดสินที่ใช้ พื้นที่ O (log  n ) ไม่สามารถใช้เวลามากกว่า 2 ^{O (log  n )}  =  n ^{O (1)}เนื่องจากนี่คือจำนวนการกำหนดค่าที่เป็นไปได้ทั้งหมด

นอกจากนี้ Lยังมีความสัมพันธ์กับคลาสNCในลักษณะต่อไปนี้: NC ¹  ⊆  L  ⊆  NL  ⊆  NC ²กล่าวคือ เมื่อมีคอมพิวเตอร์แบบขนานC ที่มีจำนวน โปรเซสเซอร์เป็นพหุนามO ( n ^k ) สำหรับค่าคงที่ kบางค่า ปัญหาใดๆ ที่สามารถแก้ไขได้บนCในเวลาO (log  n ) จะอยู่ใน Lและปัญหาใดๆ ในLสามารถแก้ไขได้ในเวลาO (log ²  n ) บน C

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

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

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

ปัญหาเปิดที่สำคัญได้แก่L  =  Pหรือ ไม่ ^{[ 2 ]}และL  =  NL หรือ ไม่^{[ 7 ]} ยังไม่เป็นที่ทราบแน่ชัดด้วยซ้ำว่าL  =  NP หรือ ไม่^{[ 8 ]}

กลุ่มปัญหาฟังก์ชัน ที่เกี่ยวข้อง คือFL FL มักใช้ในการกำหนดการลดรูปของลอการิทึมสเป ซ

เช่นเดียวกับที่ตัวอักษรPมีรูปแบบสุ่มหลายแบบ ได้แก่BPP , ZPP , PPและRP ตัวอักษร Lก็มีรูปแบบสุ่มหลายแบบเช่นกัน

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

• นอกเหนือจากเทปปกติของเครื่องทัวริงแบบลอการิทึมสเปซแล้ว เครื่องนี้ยังรับเทปที่บรรจุบิตแบบสุ่มได้อีกด้วย
• ค่าสุ่มนั้นเป็นแบบอ่านอย่างเดียวและเคลื่อนที่ได้ทางเดียว กล่าวคือ หัวอ่านบนเทปสุ่มสามารถเคลื่อนที่ได้เพียงทิศทางเดียวเท่านั้น ในการอ้างอิงบิตสุ่มก่อนหน้า เครื่องจะต้องจัดเก็บบิตนั้นไว้ในเทปทำงานก่อน
• เครื่องจักรทัวริงต้องหยุดทำงานทุกครั้งที่มีการป้อนข้อมูลและทุกครั้งที่มีการสุ่มเทป
• ถ้าคำตอบคือ 'ใช่' เครื่องจะยอมรับด้วยความน่าจะเป็นอย่างน้อย 2/3 ถ้าคำตอบคือ 'ไม่ใช่' เครื่องจะปฏิเสธด้วยความน่าจะเป็นอย่างน้อย 2/3

มีอยู่ในNC ²ซึ่งมีอยู่^ใน P [ ^{9 ]}

BP•LถูกกำหนดเหมือนกับBPLยกเว้นว่าเครื่องได้รับอนุญาตให้อ่านเทปสุ่มทั้งไปข้างหน้าและย้อนกลับ ประกอบด้วยBPLนอกจากนี้ยังเท่ากับคลาสของภาษาที่เกือบจะเป็น logspace อย่างแน่นอน: ภาษาหนึ่งเกือบจะเป็น logspace ถ้า^{เมื่อ}เทียบกับออราเคิลเกือบทุกตัว ภาษานั้นอยู่ในL ^{[ 10} ]

ZP•Lถูกกำหนดไว้เหมือนกับBP•Lยกเว้นว่าเครื่องอาจส่งออก "ไม่ทราบ" และต้องไม่เกิดข้อผิดพลาด (เช่น ยอมรับเมื่อคำตอบคือ 'ไม่' และในทางกลับกัน) ความสัมพันธ์ของZP•LกับBP•Lเหมือนกับความสัมพันธ์ของZPPกับBPPโดยมีBPL อยู่ภายใน และถูกบรรจุอยู่ภายในBP• ^L [ ^{10 ]}

L แบบสุ่ม ( RL ) ถูกกำหนดไว้ในลักษณะเดียวกับBPL :

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

นอกจากนี้ จะต้องทำงานในเวลาพหุนามเสมอ (มิฉะนั้นเราจะได้NL ^{เท่านั้น} ) เป็นที่สงสัยอย่างยิ่งว่าRL = L [ ^{11 ]}

ทั้งBPLและRLอยู่ใน^คลาสของ Steve [ ^{12 ]}

ความน่าจะเป็น L ( PL ) มีความสัมพันธ์กับL ในลักษณะเดียว กับที่PPมีต่อP :

• ถ้าคำตอบคือ 'ใช่' ให้ยอมรับด้วยความน่าจะเป็นอย่างน้อย 1/2
• ถ้าคำตอบคือ 'ไม่' ให้ปฏิเสธด้วยความน่าจะเป็นอย่างน้อย 1/2

ประกอบด้วยBPLและบรรจุ^โดย NC ² [ ^{13 ]}

ค่า Lนั้นต่ำสำหรับตัวมันเอง เพราะสามารถจำลองการสืบค้นข้อมูลของ Oracle ในพื้นที่บันทึก (โดยคร่าวๆ คือ "การเรียกใช้ฟังก์ชันที่ใช้พื้นที่บันทึก") ในพื้นที่บันทึก โดยใช้พื้นที่เดียวกันซ้ำสำหรับแต่ละการสืบค้น

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

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

• L/poly เป็นรูปแบบที่ไม่สม่ำเสมอของ L ที่สามารถจับความซับซ้อนของ โปรแกรมแตกแขนงขนาดพหุนามได้