ในวิทยาการคอมพิวเตอร์ปัญหาการเชื่อมต่อแบบ stหรือSTCONเป็นปัญหาการตัดสินใจที่ถามว่า สำหรับจุดยอดsและtในกราฟแบบมี ทิศทาง จุด tสามารถเข้าถึงได้จากจุด sหรือไม่

ในทางทฤษฎี ปัญหาการตัดสินใจกำหนดโดย

PATH = { ⟨ D ,  s ,  t ⟩ | Dเป็นกราฟแบบมีทิศทางที่มีเส้นทางจากจุดยอด s ไปยังt }

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

ส่วนเติมเต็มของst-connectivityซึ่งเรียกว่าst-non-connectivityก็อยู่ในคลาส NL เช่นกัน เนื่องจาก NL = coNL ตามทฤษฎีบท Immerman– Szelepcsényi

โดยเฉพาะอย่างยิ่ง ปัญหาของst-connectivityนั้นเป็น ปัญหา NL-complete อย่างแท้จริง กล่าวคือ ทุกปัญหาในกลุ่ม NL สามารถลดรูปได้เป็นการเชื่อมต่อภายใต้การลดรูป log-spaceซึ่งยังคงเป็นจริงสำหรับกรณีที่แข็งแกร่งกว่าของการลดรูปอันดับแรก ( Immerman 1999 , หน้า 51) การลดรูป log-space จากภาษาใดๆ ใน NL ไปยัง STCON ดำเนินการดังนี้: พิจารณาเครื่องจักรทัวริง log-space แบบไม่กำหนด M ที่ยอมรับภาษาใน NL เนื่องจากมีเพียงพื้นที่ลอการิทึมบนเทปทำงาน สถานะที่เป็นไปได้ทั้งหมดของเครื่องจักรทัวริง (โดยที่สถานะคือสถานะของเครื่องจักรสถานะจำกัดภายใน ตำแหน่งของหัว และเนื้อหาของเทปทำงาน) จึงมีจำนวนพหุนาม แมปสถานะที่เป็นไปได้ทั้งหมดของเครื่องจักร log-space แบบกำหนดไปยังจุดยอดของกราฟ และวางขอบระหว่าง u และ v หากสถานะ v สามารถเข้าถึงได้จาก u ภายในหนึ่งขั้นตอนของเครื่องจักรแบบไม่กำหนด ตอนนี้ปัญหาที่ว่าเครื่องจะยอมรับหรือไม่นั้น ก็เหมือนกับปัญหาที่ว่ามีเส้นทางจากสถานะเริ่มต้นไปยังสถานะที่ยอมรับได้หรือไม่

ทฤษฎีบทของ Savitchรับประกันว่าอัลกอริทึมสามารถจำลองได้ในพื้นที่เชิงกำหนด O (log ²  n )

ปัญหาเดียวกันนี้สำหรับกราฟแบบไม่มีทิศทางเรียกว่าการเชื่อมต่อ st แบบไม่มีทิศทางและได้รับการพิสูจน์แล้วว่าอยู่ในLโดยOmer Reingoldงานวิจัยนี้ทำให้เขาได้รับรางวัล Grace Murray Hopper Award ประจำปี 2005 การเชื่อมต่อ st แบบไม่มีทิศทางเป็นที่ทราบกันดีอยู่แล้วว่าสมบูรณ์สำหรับคลาสSLดังนั้นงานของ Reingold จึงแสดงให้เห็นว่า SL เป็นคลาสเดียวกับ L สำหรับกราฟแบบสลับ ปัญหานี้เป็นปัญหาP-สมบูรณ์ ( Immerman 1999 , หน้า 54)