Complexity classes
คลาสที่ซับซ้อน
อ่าน 1 นาทีคลาสความซับซ้อน
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ คลาสความซับซ้อนคือชุดของปัญหาการคำนวณ "ที่ มีความซับซ้อนตามทรัพยากรที่เกี่ยวข้อง" ทรัพยากรสองอย่างที่วิเคราะห์กันบ่อยที่สุดคือเวลาและหน่วยความจำ
อ่าน 1 นาทีเอ็นไทม์
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนNTIME( f ( n ))คือเซตของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบไม่กำหนดซึ่งทำงานในเวลาO ( f ( n ))...
อ่าน 1 นาทีเอพีเอ็กซ์
Approximation algorithmsในทฤษฎีความซับซ้อนของการคำนวณคลาสAPX (ย่อมาจาก "approximable") คือเซตของปัญหาการหาค่าเหมาะสมที่สุดแบบNP...
อ่าน 1 นาทีNP (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ NP ( nondeterministic polynomial time ) เป็นคลาสความซับซ้อนที่ใช้ในการจำแนกปัญหาการตัดสินใจ NP...
อ่าน 1 นาทีอี (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนEคือเซตของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบกำหนดได้ในเวลา 2 O ( n )และจึงเท่ากับคลาสความซับซ้อนDTIME (2 O ( n ) )
อ่าน 1 นาทีSNP (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ SNP (จากStrict NP ) คือกลุ่มความซับซ้อนที่มีกลุ่มย่อยจำกัดของNPโดยอาศัยลักษณะเชิงตรรกะในแง่ของ คุณสมบัติ...
อ่าน 1 นาทีรายการหัวข้อเกี่ยวกับความสามารถในการคำนวณและความซับซ้อน
Complexity classesนี่คือรายการหัวข้อเกี่ยวกับความสามารถในการคำนวณและความซับซ้อนโดยอ้างอิงจากหน้าวิกิพีเดีย
อ่าน 1 นาทีFP (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนFPคือเซตของปัญหาฟังก์ชันที่สามารถแก้ไขได้โดยเครื่องทัวริงแบบกำหนดได้ในเวลาพหุนาม...
อ่าน 1 นาทีเวลาพсевโดพหุนาม
Analysis of algorithmsในทฤษฎีความซับซ้อนของการคำนวณ อัลกอริทึมเชิงตัวเลขจะทำงานในเวลาพсевдоพหุนามหากเวลาทำงานถูกจำกัดจากด้านบนด้วย ฟังก์ชัน พหุนามของตัวแปรสองตัว ได้แก่ค่าตัวเลขของอินพุต...
อ่าน 1 นาทีเอซี0
Circuit complexityAC 0 (วงจรสลับ) เป็นคลาสความซับซ้อนที่ใช้ในความซับซ้อนของวงจรเป็นคลาสที่เล็กที่สุดใน ลำดับชั้น ACและประกอบด้วยวงจรทุกตระกูลที่มีความลึก O(1) และขนาดพหุนาม โดยมีเกต ANDและเกต OR...
อ่าน 1 นาทีเวลาพหุนามที่แข็งแกร่ง
Complexity classesในวิทยาการคอมพิวเตอร์อัลกอริทึมเวลาพหุนาม (polynomial-time algorithm)โดยทั่วไปแล้วคืออัลกอริทึมที่มีเวลาการทำงานสูงสุดไม่เกินฟังก์ชันพหุนามของขนาดอินพุต...
อ่าน 1 นาทีเวลาหมดอายุ
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนEXPTIME (บางครั้งเรียกว่าEXPหรือDEXPTIME ) คือเซตของปัญหาการตัดสินใจ ทั้งหมด ที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบกำหนดได้...
อ่าน 1 นาทีลำดับชั้นเลขชี้กำลัง
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณลำดับชั้นเลขชี้กำลังเป็นลำดับชั้นของคลาสความซับซ้อนที่เป็นอนาล็อกของลำดับชั้นพหุนามในเวลาเลขชี้กำลังเช่นเดียวกับในทฤษฎีความซับซ้อนอื่นๆ คำว่า...
อ่าน 1 นาทีเวลากึ่งพหุนาม
Analysis of algorithmsในทฤษฎีความซับซ้อนของ การคำนวณ และ การวิเคราะห์อัลกอริทึม อัลกอริทึมจะกล่าวได้ว่าใช้เวลาแบบกึ่งพหุนาม (quasi-polynomial time)หากความซับซ้อนของเวลา ของอัลกอริทึมนั้น มี...
อ่าน 1 นาทีพี (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณPหรือที่รู้จักกันในชื่อPTIMEหรือDTIME ( n O(1) ) เป็นคลาสความซับซ้อน พื้นฐาน ประกอบด้วยปัญหาการตัดสินใจ ทั้งหมด
อ่าน 1 นาทีFNP (ความซับซ้อน)
Binary relationsในทฤษฎีความซับซ้อนของการคำนวณกลุ่มความซับซ้อนFNPคือส่วนขยายของกลุ่มปัญหาการตัดสินใจNP ที่นำไปสู่ปัญหาฟังก์ชัน ชื่อนี้อาจไม่ตรงกับความเป็นจริงนัก...
อ่าน 1 นาทีรายการคลาสความซับซ้อน
Complexity classesนี่คือรายการของระดับความซับซ้อนในทฤษฎีความซับซ้อนเชิงคำนวณสำหรับหัวข้ออื่นๆ ที่เกี่ยวข้องกับการคำนวณและความซับซ้อน โปรดดูรายการ หัวข้อเกี่ยวกับการคำนวณได้และความซับซ้อน
อ่าน 1 นาทีเอ็กซ์พีสเปซ
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ EXPSPACE คือเซต ของ ปัญหาการตัดสินใจทั้งหมดที่สามารถแก้ไขได้โดยเครื่องจักรทัวริง แบบกำหนดได้ ในปริภูมิเอกซ์โพเนนเชียลกล่าวคือ ในปริภูมิที่
อ่าน 1 นาทีแผนการประมาณค่าแบบใช้เวลาพหุนาม
Approximation algorithmsในวิทยาการคอมพิวเตอร์ (โดยเฉพาะด้านอัลกอริธึม ) แผนการประมาณค่าแบบใช้เวลาพหุนาม ( PTAS ) เป็น อัลกอริธึมประมาณค่าประเภทหนึ่งสำหรับปัญหาการหาค่าเหมาะสมที่สุด (ส่วนใหญ่จะ...
อ่าน 1 นาทีNE (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนNEคือเซตของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องทัวริงแบบไม่กำหนดในเวลา มันคล้ายกับNEXPTIME ซึ่ง เป็น
อ่าน 1 นาทีพี-สมบูรณ์
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณปัญหาการตัดสินใจเรียกว่าP-complete ( สมบูรณ์สำหรับชั้นความซับซ้อนP )...
อ่าน 1 นาทีPPAD (ความซับซ้อน)
Complexity classesในวิทยาการคอมพิวเตอร์ PPAD ( “Polynomial Parity Arguments on Directed graphs”) เป็นคลาสความซับซ้อน ที่ Christos Papadimitriouแนะนำในปี 1994 PPAD
อ่าน 1 นาทีเน็กซ์ไทม์
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณกลุ่มความซับซ้อนNEXPTIME (บางครั้งเรียกว่าNEXP ) คือเซตของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบไม่กำหนดโดย...
อ่าน 1 นาทีทั้งหมด (ความซับซ้อน)
Complexity classesในทฤษฎีความสามารถในการคำนวณและ ความซับซ้อน ALLคือกลุ่มของปัญหาการตัดสินใจทั้งหมด