Complexity classes
คลาสที่ซับซ้อน - หน้า 2
อ่าน 1 นาทีPR (ความซับซ้อน)
Complexity classesPRคือคลาสความซับซ้อน ของ ฟังก์ชันเรียกซ้ำพื้นฐานทั้งหมด หรือกล่าวอีกนัยหนึ่ง คือเซตของภาษาเชิงรูปธรรม ทั้งหมด ที่สามารถหาคำตอบได้ภายในเวลาที่กำหนดโดยฟังก์ชันดังกล่าว...
อ่าน 1 นาทีฟังก์ชันเรียกซ้ำพื้นฐาน
CS1 Hungarian-language sources (hu)คำว่า"พื้นฐาน"เดิมทีได้รับการแนะนำโดยLászló Kalmárในบริบทของทฤษฎีความสามารถในการคำนวณ เขาได้กำหนดคลาสของฟังก์ชันเรียกซ้ำพื้นฐาน ( "ฟังก์ชันพื้นฐานของ Kalmár" )...
อ่าน 1 นาทีปัญหาความเหมือนกันของกราฟ
Complexity classesปัญหาความเหมือนกันของกราฟคือปัญหาการคำนวณ เพื่อพิจารณาว่า กราฟจำกัดสอง กราฟ มีความเหมือนกัน หรือ ไม่
อ่าน 1 นาทีNL (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ NL ( Nondeterministic Logarithmic - space) คือกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบไม่กำหนด...
อ่าน 1 นาทีNC (ความซับซ้อน)
Circuit complexityในทฤษฎีความซับซ้อนของการคำนวณคลาสNC (ย่อมาจาก "Nick's Class") คือเซตของปัญหาการตัดสินใจที่สามารถตัดสินได้ในเวลาพหุโลการิทึมบนคอมพิวเตอร์แบบขนานที่มีจำนวนโปรเซสเซอร์เป็นพหุนาม...
อ่าน 1 นาที♯P-สมบูรณ์
Complexity classesปัญหา#P-complete (อ่านว่า "ชาร์ป พี คอมพลีท", "นัมเบอร์ พี คอมพลีท" หรือ "แฮช พี คอมพลีท")...
อ่าน 1 นาทีPSPACE เสร็จสมบูรณ์
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณปัญหาการตัดสินใจจะเรียกว่าPSPACE-complete ก็ต่อเมื่อสามารถแก้ไขได้โดยใช้หน่วยความจำในปริมาณที่เป็นพหุนามตามความยาวของข้อมูลนำเข้า ( ปริภูมิพหุนาม )...
อ่าน 1 นาทีแผนการประมาณค่าแบบใช้เวลาพหุนามอย่างสมบูรณ์
Approximation algorithmsอัลกอริทึมการประมาณค่าแบบใช้เวลาพหุนามอย่างสมบูรณ์ (FPTAS)เป็นอัลกอริทึมสำหรับค้นหาคำตอบโดยประมาณของปัญหาเกี่ยวกับฟังก์ชันโดยเฉพาะอย่างยิ่งปัญหาการหาค่าเหมาะสม ที่สุด FPTAS...
อ่าน 1 นาทีโค-เอ็นพี-สมบูรณ์
Complexity classesในทฤษฎีความซับซ้อนปัญหาการคำนวณที่เป็นco-NP-completeคือปัญหาที่ยากที่สุดในco-NPในแง่ที่ว่าปัญหาใดๆ ใน co-NP สามารถแปลงรูปแบบใหม่ได้เป็นกรณีพิเศษของปัญหา co-NP-complete ใดๆ...
อ่าน 1 นาทีความแข็งระดับ NP
CS1: long volume valueในทฤษฎีความซับซ้อนของการคำนวณปัญหาการคำนวณHเรียกว่าNP-hardถ้าสำหรับทุกปัญหาLที่สามารถแก้ไขได้ในเวลาพหุนามที่ไม่แน่นอนจะมี การลดรูป จากLไปยังH ใน เวลาพหุนามนั่นคือ...
อ่าน 1 นาทีแอล (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ L (หรือที่รู้จักกันในชื่อLSPACE , LOGSPACEหรือDLOGSPACE )
อ่าน 1 นาทีเอ็นสเปซ
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณพื้นที่แบบไม่กำหนด (Non-deterministic space หรือNSPACE)คือทรัพยากรการคำนวณที่อธิบายพื้นที่หน่วยความจำสำหรับเครื่องทัวริงแบบไม่กำหนดซึ่งเป็นส่วนที่ไม่กำ...
อ่าน 1 นาทีพีเอสสเปซ
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ PSPACE คือเซตของปัญหาการตัดสินใจ ทั้งหมด ที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงโดยใช้พื้นที่ในปริมาณพหุ นาม
อ่าน 1 นาทีปัญหาดาวแหวน
Complexity classesปัญหา Ring Star ( RSP ) เป็นปัญหาNP-hard ในการเพิ่มประสิทธิภาพเชิงการจัดเรียงในกราฟผสมแบบถ่วงน้ำหนักที่สมบูรณ์ปัญหา Ring Star มีเป้าหมายเพื่อค้นหากราฟย่อย Ring Star...
อ่าน 1 นาทีดีไทม์
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณ DTIME (หรือTIME ) คือทรัพยากรการ คำนวณ ของเวลา ในการคำนวณ สำหรับเครื่องจักรทัวริงแบบกำหนดได้มันแสดงถึงปริมาณเวลา (หรือจำนวนขั้นตอนการคำนวณ)...
อ่าน 1 นาทีปัญหาที่ไม่ใช่ปัญหาพื้นฐาน
CS1 maint: work parameter with ISBNในทฤษฎีความซับซ้อนของการคำนวณปัญหา ที่ไม่ใช่ปัญหาพื้นฐานคือปัญหาที่ไม่ใช่สมาชิกของคลาสELEMENTARYบางครั้งคลาสนี้จะถูกเรียกว่า NONELEMENTARY นั่นคือ
อ่าน 1 นาทีดล็อกไทม์
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณDLOGTIMEคือคลาสความซับซ้อนของปัญหาการคำนวณ ทั้งหมด ที่สามารถแก้ไขได้ด้วยปริมาณเวลาการคำนวณแบบลอการิทึมบนเครื่องทัวริง แบบกำหนดได้
อ่าน 1 นาทีNP-easy
Complexity classesในทฤษฎีความซับซ้อนกลุ่มความซับซ้อนNP-easyคือเซตของปัญหาฟังก์ชันที่สามารถแก้ไขได้ในเวลาพหุนาม โดย เครื่องจักรทัว ริ งเชิงกำหนดที่มีออราเคิลสำหรับปัญหาการตัดสินใจ บางอย่าง ในNP
อ่าน 1 นาทีRE (ความซับซ้อน)
Complexity classesในทฤษฎีความสามารถในการคำนวณและทฤษฎีความซับซ้อนของการคำนวณRE ( recursively enumerable ) คือคลาสของปัญหาการตัดสินใจที่สามารถตรวจสอบคำตอบ 'ใช่'...
อ่าน 1 นาทีลำดับชั้นพหุนาม
Complexity classesในทฤษฎีความซับซ้อนของ การคำนวณ ลำดับชั้นพหุนาม (บางครั้งเรียกว่าลำดับชั้นเวลาพหุนาม ) เป็นลำดับชั้นของคลาสความซับซ้อนที่ขยายคลาสNPและco-NP
อ่าน 1 นาทีUP (ความซับซ้อน)
Complexity classesในทฤษฎีความซับซ้อน UP ( unambiguous non-deterministic polynomial-time ) คือกลุ่มความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้ในเวลาพหุนามบนเครื่องทัวริงที่ไม่กำกวม (...
อ่าน 1 นาทีLOGCFL
Complexity classesในทฤษฎีความซับซ้อนของการคำนวณLOGCFLคือคลาสความซับซ้อน ที่ประกอบด้วย ปัญหาการตัดสินใจทั้งหมดที่สามารถลดขนาดลงในพื้นที่ลอการิทึมให้เป็นภาษาที่ไม่ขึ้นกับบริบทได้...
อ่าน 1 นาทีNP-ระดับกลาง
Complexity classesในความซับซ้อนของการคำนวณปัญหาที่อยู่ในคลาสความซับซ้อนNPแต่ไม่อยู่ในคลาสPหรือNP-completeเรียกว่าNP-intermediateและคลาสของปัญหาดังกล่าวเรียกว่าNPI ทฤษฎีบทของ Ladner ซึ่งแสดงในปี...
อ่าน 1 นาทีACC 0
Circuit complexityACC 0บางครั้งเรียกว่าACCเป็นคลาสของแบบจำลองการคำนวณและปัญหาที่กำหนดในความซับซ้อนของวงจรซึ่งเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี คลาสนี้ถูกกำหนดโดยการเพิ่มคลาสAC 0ของ...