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

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

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

ตัวอย่างของปัญหาที่ศึกษาในการปรับโครงสร้างใหม่ ได้แก่:

• เกมหรือปริศนา เช่นปริศนา 15หรือลูกบาศก์รูบิกปริศนาประเภทนี้มักจะสามารถจำลองทางคณิตศาสตร์ได้โดยใช้ทฤษฎีกลุ่มการเรียงสับเปลี่ยนซึ่งนำไปสู่อัลกอริธึมที่รวดเร็วในการพิจารณาว่าสถานะต่างๆ เชื่อมต่อกันหรือไม่ อย่างไรก็ตาม การหาเส้นผ่านศูนย์กลางของปริภูมิสถานะหรือเส้นทางที่สั้นที่สุดระหว่างสองสถานะอาจยากกว่า ตัวอย่างเช่น สำหรับลูกบาศก์รูบิกบางเวอร์ชัน เส้นผ่านศูนย์กลางของปริภูมิสถานะคือและความซับซ้อนของการหาคำตอบที่สั้นที่สุดยังไม่เป็นที่ทราบ แต่สำหรับเวอร์ชันทั่วไปของปริศนา (ซึ่งบางหน้าของลูกบาศก์ไม่มีป้ายกำกับ) ถือเป็นNP-hard [ ^{1 ] ปริศนา}การจัดเรียงใหม่แบบอื่นๆ เช่นโซโคบันอาจจำลองเป็นการจัดเรียงโทเค็นใหม่แต่ขาดโครงสร้างเชิงทฤษฎีกลุ่ม สำหรับปัญหาดังกล่าว ความซับซ้อนอาจสูงขึ้น โดยเฉพาะอย่างยิ่ง การทดสอบการเข้าถึงสำหรับโซโคบันเป็นPSPACE- complete ^{[ 2 ]}${\displaystyle n\times n\times n}$${\displaystyle \Theta (n^{2}/\log n)}$
• ระยะทางการหมุนในต้นไม้ไบนารีและปัญหาที่เกี่ยวข้องกับระยะทางการพลิกในกราฟพลิกการหมุนคือการดำเนินการที่เปลี่ยนโครงสร้างของต้นไม้ไบนารีโดยไม่ส่งผลกระทบต่อลำดับจากซ้ายไปขวาของโหนด มักใช้เพื่อปรับสมดุลต้นไม้ค้นหาไบนารีระยะทางการหมุนคือจำนวนการหมุนขั้นต่ำที่จำเป็นในการแปลงต้นไม้หนึ่งเป็นอีกต้นไม้หนึ่ง พื้นที่สถานะเดียวกันนี้ยังจำลองการแบ่งสามเหลี่ยมของรูปหลายเหลี่ยมนูน และการเคลื่อนไหวที่ "พลิก" การแบ่งสามเหลี่ยมหนึ่งไปเป็นการแบ่งสามเหลี่ยมอื่นโดยการลบเส้นทแยงมุมหนึ่งของรูปหลายเหลี่ยมและแทนที่ด้วยเส้นทแยงมุมอื่น ปัญหาที่คล้ายกันนี้ได้รับการศึกษาเกี่ยวกับการแบ่งสามเหลี่ยมประเภทอื่นด้วยเช่นกัน ระยะทางการหมุนสูงสุดที่เป็นไปได้ระหว่างต้นไม้สองต้นที่มีจำนวนโหนดที่กำหนดเป็นที่ทราบกันดี^{[ 3 ]}แต่ยังคงเป็นปัญหาที่เปิดอยู่ว่าระยะทางการหมุนระหว่างต้นไม้สองต้นใดๆ สามารถหาได้ในเวลาพหุนามหรือ ไม่ ^{[ 4 ]}ปัญหาที่คล้ายกันสำหรับระยะทางการพลิกระหว่างการแบ่งสามเหลี่ยมของชุดจุดหรือรูปหลายเหลี่ยมที่ไม่นูนนั้นเป็นปัญหา NP-hard ^{[ 5 ] [ 6 ]}
• การกำหนดค่าใหม่ของการระบายสีกราฟการเคลื่อนไหวที่ได้รับการพิจารณาสำหรับการกำหนดค่าใหม่ของการระบายสี ได้แก่ การเปลี่ยนสีของจุดยอดเดียว หรือการสลับสีของสายโซ่ Kempeเมื่อจำนวนสีมีอย่างน้อยสองสีบวกกับความเสื่อมของกราฟ พื้นที่สถานะของการระบายสีจุดยอดเดียวจะเชื่อมต่อกัน และสมมติฐานของ Cerecedaชี้ให้เห็นว่ามีเส้นผ่านศูนย์กลางพหุนาม สำหรับสีที่น้อยกว่า กราฟบางกราฟมีพื้นที่สถานะที่ไม่เชื่อมต่อกัน สำหรับการระบายสี 3 สี การทดสอบการเชื่อมต่อทั่วโลกของพื้นที่สถานะการระบายสีจุดยอดเดียวเป็นco-NP-complete [ ^{7 ] แต่}เมื่อการระบายสีสองแบบสามารถกำหนดค่าใหม่ให้กันและกันได้ ลำดับการกำหนดค่าใหม่ที่สั้นที่สุดสามารถพบได้ในเวลาพหุนาม^{[ 8 ]}สำหรับสีมากกว่าสามสี การกำหนดค่าจุดยอดเดียวเป็น PSPACE-complete ^{[ 9 ]}
• ตรรกะข้อจำกัดแบบไม่กำหนด (Nondeterministic constraint logic)เป็นปัญหาเชิงการจัดเรียง (combinatorial problem) เกี่ยวกับการวางแนวของกราฟลูกบาศก์ที่มีขอบสีแดงและสีน้ำเงิน ในสถานะที่ถูกต้องของระบบ แต่ละจุดยอดจะต้องมีขอบสีน้ำเงินอย่างน้อยหนึ่งขอบหรืออย่างน้อยสองขอบที่เข้ามายังจุดยอดนั้น การเคลื่อนที่ในปริภูมิสถานะนี้จะกลับทิศทางการวางแนวของขอบเพียงขอบเดียวในขณะที่ยังคงรักษาข้อจำกัดเหล่านี้ไว้การทดสอบว่าปริภูมิสถานะที่ได้เชื่อมต่อกันหรือไม่ หรือว่าสองสถานะสามารถเข้าถึงกันได้หรือไม่นั้น เป็นปัญหา PSPACE -complete แม้ว่ากราฟพื้นฐานจะมี แบนด์วิดท์ ที่จำกัด ก็ตาม^{[ 10 ]}ผลลัพธ์ความยากเหล่านี้มักถูกใช้เป็นพื้นฐานของการลดทอนที่พิสูจน์ว่าปัญหาการกำหนดค่าใหม่แบบอื่น เช่น ปัญหาที่เกิดขึ้นจากเกมและปริศนา ก็เป็นปัญหาที่ยากเช่นกัน^{[ 11 ]}

• แหล่งข้อมูลเกี่ยวกับการจัดเรียงใหม่เชิงการจัดเรียง (รวมถึงบรรณานุกรมที่ไม่ครบถ้วนสมบูรณ์ )