We now come to the issues that make computer scientists look to the quan-<\/p>\n\n\n\n
tum paradigm for answering some of their questions on e\ufb03cient algorithms.<\/p>\n\n\n\n
E\ufb03ciency is quanti\ufb01ed in terms of how the resources used for the compu-<\/p>\n\n\n\n
tation scale with the number of input bits n. Typically, polynomial scaling<\/p>\n\n\n\n
is termed \u201ce\ufb03cient\u201d while exponential scaling is not. Resources are typically<\/p>\n\n\n\n
time, space and energy, though the last one is less a theoretical concern than<\/p>\n\n\n\n
for the physical implementation.<\/p>\n\n\n\n
When analyzing the e\ufb03ciency of an algorithm, it is desirable to factor out<\/p>\n\n\n\n
dependencies on the kind of computer the algorithm may be implemented on.<\/p>\n\n\n\n
The resulting features are to be intrinsic to the mathematical problem itself,<\/p>\n\n\n\n
and are de\ufb01ned in terms of how they scale as a function of the input size,<\/p>\n\n\n\n
rather than in absolute terms. These behaviors are termed complexity.<\/p>\n\n\n\n
Time complexity is the most commonly considered aspect of e\ufb03ciency of<\/p>\n\n\n\n
algorithms, and can be quanti\ufb01ed by the number of elementary steps, such as<\/p>\n\n\n\n
the addition of two numbers, in the execution of an algorithm. Space complex-<\/p>\n\n\n\n
ity can be quanti\ufb01ed by the amount of memory to be allocated to the execution<\/p>\n\n\n\n
of the algorithm. While the actual complexity of a problem depends on the<\/p>\n\n\n\n
particular algorithm used and also the size of the input, we try to generalize<\/p>\n\n\n\n
the concept by considering the asymptotic behavior, as the input size becomes<\/p>\n\n\n\n
very large.<\/p>\n\n\n\n
Computational complexity is often quanti\ufb01ed in three di\ufb00erent ways. The<\/p>\n\n\n\n
way in which an algorithm scales as n is expressed in the following ways for<\/p>\n\n\n\n
large n:<\/p>\n\n\n\n
1. O(g(n)) (big oh): which speci\ufb01es that the function g(n) is the upper<\/p>\n\n\n\n
bound on the behavior of a resource;<\/p>\n\n\n\n
2. \u03a9(g(n)) (big omega): speci\ufb01es that the function g(n) is the lower bound<\/p>\n\n\n\n
on the behavior of a resource;<\/p>\n\n\n\n
3. \u0398(g(n)) (big theta): this is the strongest condition, when a given resource<\/p>\n\n\n\n
scales as both O(g(n)) and \u03a9(g(n)) with the same function g(n).<\/p>\n\n\n\n
The \ufb01rst type, O which gives the upper bound, is the most commonly used.<\/p>\n\n\n\n
Example 6.4.1. Let\u2019s look at the time complexity of simple arithmetic oper-<\/p>\n\n\n\n
ations.<\/p>\n\n\n\n
\u2022 Addition of two n-bit integers takes exactly n steps and has complexity<\/p>\n\n\n\n
\u0398(n).<\/p>\n\n\n\n
\u2022 Multiplication of two n-bit integers by the usual brute force method<\/p>\n\n\n\n
<\/p>\n\n\n\n
Computation Models and Computational Complexity 117<\/p>\n\n\n\n
takes n \u2212 1 additions and at most n carries. Thus the complexity is<\/p>\n\n\n\n
O(n<\/p>\n\n\n\n
2<\/p>\n\n\n\n
).<\/p>\n\n\n\n
\u2022 Matrix multiplication of two n \u00d7n matrices takes n multiplications and<\/p>\n\n\n\n
n additions, and therefore is of complexity O(n \u00d7 n<\/p>\n\n\n\n
2<\/p>\n\n\n\n
) = O(n<\/p>\n\n\n\n
3<\/p>\n\n\n\n
). If the<\/p>\n\n\n\n
matrices are not square, but m \u00d7 n and n \u00d7 l then the complexity is<\/p>\n\n\n\n
O(mnl).<\/p>\n\n\n\n
Box 6.2: Complexity Classes<\/p>\n\n\n\n
There exists a plethora of complexity classes in this vast and deep subject<\/p>\n\n\n\n
and we list some of the more important ones here. These complexity classes<\/p>\n\n\n\n
assume a Turing model for the computer.<\/p>\n\n\n\n
\u2022 P (Polynomial time): This class contains problems that are solvable in<\/p>\n\n\n\n
polynomial time, that is they are of O(n<\/p>\n\n\n\n
k<\/p>\n\n\n\n
) for some k, on a deterministic<\/p>\n\n\n\n
Turing machine.<\/p>\n\n\n\n
\u2022 NP (Non-deterministic polynomial time): this is the class of decision<\/p>\n\n\n\n
problem (with only \u201cyes\u201d or \u201cno\u201d answers) for which, given a solution, it<\/p>\n\n\n\n
can be veri\ufb01ed in polynomial time in a non-deterministic Turing machine<\/p>\n\n\n\n
model. It is yet an unsolved problem as to whether an NP problem can<\/p>\n\n\n\n
be solved in polynomial time. Examples include integer factorization and<\/p>\n\n\n\n
discrete logarithm.<\/p>\n\n\n\n
\u2022 coNP consists of decision problems whose complement is in NP.<\/p>\n\n\n\n
\u2022 NP-complete (NPC) is the class of problems containing the hardest<\/p>\n\n\n\n
problem in NP. This class includes problems which may be outside NP.<\/p>\n\n\n\n
Examples are the Knapsack problem, the traveling salesman problem,<\/p>\n\n\n\n
Boolean satis\ufb01ability problem.<\/p>\n\n\n\n
In some situations, especially in the quantum algorithms we are going to<\/p>\n\n\n\n
study in this book, we talk of the \u201cquery complexity\u201d of an algorithm. Here,<\/p>\n\n\n\n
the algorithm is reduced to a series of binary answers to a query made to a<\/p>\n\n\n\n
function evaluator looked upon as a black box, whose functioning is unknown<\/p>\n\n\n\n
to us. This is calculated as the number of times the black box has to be queried<\/p>\n\n\n\n
to get to the solution. Of course, if the black box is replaced by a \u201cwhite box\u201d:<\/p>\n\n\n\n
the details of the circuit used to implement the function, then we can relate<\/p>\n\n\n\n
the query complexity to the actual computational complexity of the entire<\/p>\n\n\n\n
process<\/p>\n","protected":false},"excerpt":{"rendered":"
We now come to the issues that make computer scientists look to the quan- tum paradigm for answering some of their questions on e\ufb03cient algorithms. E\ufb03ciency is quanti\ufb01ed in terms of how the resources used for the compu- tation scale with the number of input bits n. Typically, polynomial scaling is termed \u201ce\ufb03cient\u201d while exponential […]<\/p>\n","protected":false},"author":1,"featured_media":4040,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[495],"tags":[],"class_list":["post-4058","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computation-models-and-computational-complexity"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/download-1.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4058","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/comments?post=4058"}],"version-history":[{"count":2,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4058\/revisions"}],"predecessor-version":[{"id":4580,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4058\/revisions\/4580"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4040"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4058"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4058"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4058"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}