Last Updated
：2025/12/05
Blum's speedup theorem
Proper noun
Japanese Meaning
（計算理論）基本的な定理の一つで、任意の複雑性測度に対し、その測度で最適な計算可能関数が存在しない、すなわち常にさらなる高速化が可能な計算可能関数が存在することを示している。
Quizzes for review
(computing theory) A fundamental theorem about the complexity of computable functions, stating that for any complexity measure there are computable functions that are not optimal with respect to that measure.
音声機能が動作しない場合はこちらをご確認ください
See correct answer
Blum's speedup theorem
Blum's speedup theorem shows that for every reasonable complexity measure there are computable functions that lack a single optimal program, because one can always find programs with progressively better resource bounds.
See correct answer
Blum's speedup theorem shows that for every reasonable complexity measure there are computable functions that lack a single optimal program, because one can always find programs with progressively better resource bounds.
音声機能が動作しない場合はこちらをご確認ください
English - English
Word Edit Setting
- Users who have edit permission for words - All Users
- Screen new word creation
- Screen word edits
- Screen word deletion
- Screen the creation of new headword that may be duplicates
- Screen changing entry name
- Users authorized to vote on judging - Editor
- Number of votes required for decision - 1
Sentence Edit Setting
- Users who have edit permission for sentences - All Users
- Screen sentence deletion
- Users authorized to vote on judging - Editor
- Number of votes required for decision - 1
Quiz Edit Setting
- Users who have edit permission for quizzes - All Users
- Users authorized to vote on judging - Editor
- Number of votes required for decision - 1
