computational complexity

American  

[kahm-pyoo-tay-shuhn-uhl-kuhm-plek-si-tee] / ˌkɑm pyuˈteɪ ʃən əl kəmˈplɛk sɪ ti /

noun

plural

computational complexities

1. Computers. an assessment or measure of the requirements, such as the number of steps, necessary to carry out a computational task.

---

computational complexity Scientific  

/ kŏm′py-tā′shə-nəl /

1. A mathematical characterization of the difficulty of a mathematical problem which describes the resources required by a computing machine to solve the problem. The mathematical study of such characterizations is called computational complexity theory and is important in many branches of theoretical computer science, especially cryptography.

---

Example Sentences

This allows for feature fusion in high resolutions at a low computational complexity.

From Science Daily • Jan. 9, 2024

In the cases of both cryptography and quantum supremacy, computational complexity theory is a very long way from being able to prove the conjectured computational limitations unconditionally.

From Nature • Sep. 12, 2017

If quantum entanglement knits together pieces of space, he says, then computational complexity may drive the growth of space — and thus bring in the elusive element of time.

From Nature • Nov. 15, 2015

One potential consequence, which he is just beginning to explore, could be a link between the growth of computational complexity and the expansion of the Universe.

From Nature • Nov. 15, 2015

He thinks physicists may have to embrace another concept from quantum information theory: computational complexity, the number of logical steps, or operations, needed to construct the quantum state of a system.

From Nature • Nov. 15, 2015