Structural complexity theory
ทฤษฎีความซับซ้อนของโครงสร้าง
ทฤษฎีบทอิมเมอร์มาน–เซเลปเซนยี
Mathematical theorems in theoretical computer scienceในทฤษฎีความซับซ้อนของการคำนวณ ทฤษฎีบท Immerman –Szelepcsényiระบุว่าคลาสความซับซ้อนของพื้นที่แบบไม่กำหนด ปิดภายใต้การเติมเต็มNeil ImmermanและRóbert Szelepcsényi...
อ่าน 1 นาทีทฤษฎีบทวาเลียนต์-วาซิรานี
Structural complexity theoryทฤษฎีบทValiant–Vaziraniเป็นทฤษฎีบทในทฤษฎีความซับซ้อนของการคำนวณที่ระบุว่า หากมีอัลกอริทึมเวลาพหุนามสำหรับUnambiguous-SATแล้วNP = RPได้รับการพิสูจน์โดยLeslie ValiantและVijay...
อ่าน 1 นาทีเอ็นแอลเอ็น
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณNLINคือคลาสของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องทัวริงแบบมัลติเทปที่ไม่กำหนดในเวลาเชิงเส้นO ( n )...
อ่าน 1 นาทีปัญหา P เทียบกับ NP
1956 in computingปัญหา P เทียบกับ NP เป็น ปัญหาสำคัญ ที่ยังแก้ไม่ตก ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีโดยคร่าวๆ แล้ว ปัญหานี้คือ ทุกปัญหาที่สามารถตรวจสอบคำตอบได้อย่างรวดเร็ว...
อ่าน 1 นาทีทฤษฎีบทของโทดะ
Structural complexity theoryทฤษฎีบทของโทดะเป็นผลลัพธ์ในทฤษฎีความซับซ้อนของการคำนวณซึ่งได้รับการพิสูจน์โดยเซอิโนะสุเกะ โทดะในบทความของเขาเรื่อง "PP ยากพอๆ กับลำดับชั้นเวลาพหุนาม" และได้รับรางวัล Gödel...
อ่าน 1 นาทีทฤษฎีบทลำดับชั้นของพื้นที่
Structural complexity theoryในทฤษฎีความซับซ้อนของการคำนวณทฤษฎีบทลำดับชั้นของพื้นที่เป็นผลลัพธ์การแยกส่วนที่แสดงให้เห็นว่าทั้งเครื่องจักรแบบกำหนดได้และแบบไม่กำหนดได้สามารถแก้ปัญหาได้มากขึ้นในพื้นที่ที่มากกว่า.
อ่าน 1 นาทีทฤษฎีลำดับชั้นเวลา
Structural complexity theoryในทฤษฎีความซับซ้อนของการคำนวณทฤษฎีบทลำดับชั้นของเวลาเป็นข้อความสำคัญเกี่ยวกับการคำนวณที่จำกัดเวลาบนเครื่องจักรทัวริงโดยคร่าวๆ แล้ว ทฤษฎีบทเหล่านี้กล่าวว่า เมื่อมีเวลามากขึ้น...
อ่าน 1 นาทีสมมติฐานเบอร์แมน-ฮาร์ทมานิส
Conjecturesในทฤษฎีความซับซ้อนเชิงโครงสร้าง ข้อสันนิษฐาน ของเบอร์แมน-ฮาร์ทมานิสเป็นข้อสันนิษฐาน ที่ยังไม่ได้รับการแก้ไข ซึ่งตั้งชื่อตามเลียวนาร์ด ซี.
อ่าน 1 นาทีทฤษฎีบทของซาวิตช์
Structural complexity theoryในทฤษฎีความซับซ้อนของการคำนวณทฤษฎีบทของ Savitchซึ่งพิสูจน์โดยWalter Savitchในปี 1970 ให้ความสัมพันธ์ระหว่าง...