Description
算法复杂度分类多达数百种，但它们之间许多有包含的关系。以下这组复杂度，从简单到复杂，有点像俄罗斯套娃，层层嵌套：它们是：P问题,NP问题，PH问题，多项式空间问题，指数时间问题。其中之前的每一个都是后面的复杂度的子集，但除NP与PH问题外，其他每两种复杂度之间是否是“真子集”（即，是否可以排除“等于”）关系，都还未证明。以下这组复杂度，也构成一组“套娃”：P问题，BPP问题，BQP问题。科学家认为BQP问题，即量子计算机能快速处理的问题，虽然含有很多NP问题，但与NP问题互不包含。但这仍然是待证明的领域。
Audio
Featured in this Episode
No persons identified in this episode.
Transcription
This episode hasn't been transcribed yet
Help us prioritize this episode for transcription by upvoting it.
0
upvotes
Popular episodes get transcribed faster
Other recent transcribed episodes
Transcribed and ready to explore now
Eric Larsen on the emergence and potential of AI in healthcare
10 Dec 2025
McKinsey on Healthcare
Reducing Burnout and Boosting Revenue in ASCs
10 Dec 2025
Becker’s Healthcare -- Spine and Orthopedic Podcast
Dr. Erich G. Anderer, Chief of the Division of Neurosurgery and Surgical Director of Perioperative Services at NYU Langone Hospital–Brooklyn
09 Dec 2025
Becker’s Healthcare -- Spine and Orthopedic Podcast
Dr. Nolan Wessell, Assistant Professor and Well-being Co-Director, Department of Orthopedic Surgery, Division of Spine Surgery, University of Colorado School of Medicine
08 Dec 2025
Becker’s Healthcare -- Spine and Orthopedic Podcast
NPR News: 12-08-2025 2AM EST
08 Dec 2025
NPR News Now
NPR News: 12-08-2025 1AM EST
08 Dec 2025
NPR News Now