 # Computational complexity theory

Скачати 327.06 Kb.
 Назва Computational complexity theory Сторінка 1/9 Дата 08.06.2012 Розмір 327.06 Kb. Тип Документи

## Computational complexity theory

In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given computational problem. This cost is usually measured in terms of abstract parameters such as time and space, called computational resources. Time represents the number of steps it takes to solve a problem and space represents the quantity of information storage required or how much memory it takes. There are often tradeoffs between time and space that have to be considered when trying to solve a computational problem. It often turns out that an alternative algorithm will require less time but more space (or vice versa) to solve a given problem. Time requirements sometimes must be amortized to determine the time cost for a well defined average case. Space requirements can be profiled over time, too, especially in consideration of a multi-user computer system.

Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. In this case, "parallelizable time" and "non-parallelizable time" are considered. The latter is important in real-time applications, and it gives a limit to how far the computation can be parallelized. Some steps must be done sequentially because they depend on the results of previous steps.

Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.

## Overview

After the theory explaining which problems can be solved and which cannot be, it was natural to ask about the relative computational difficulty of computable functions. This is the subject matter of computational complexity.

A single "problem" is an entire set of related questions, where each question is a finite-length string. For example, the problem FACTORIZE is: given an integer written in binary, return all of the prime factors of that number. A particular question is called an instance. For example, "give the factors of the number 15" is one instance of the FACTORIZE problem.

The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. To understand this intuitively, consider the example of an instance that is n bits long that can be solved in nІ steps. In this example we say the problem has a time complexity of nІ. Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use Big O notation. If a problem has time complexity O(nІ) on one typical computer, then it will also have complexity O(nІp(n)) on most other computers for some polynomial p(n), so this notation allows us to generalize away from the details of a particular computer.

Example: Mowing grass has linear complexity because it takes double the time to mow double the area. However, looking up something in a dictionary has only logarithmic complexity because a double sized dictionary only has to be opened one time more (e.g. exactly in the middle - then the problem is reduced to the half).

^

## Decision problems

Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always YES/NO. For example, the problem IS-PRIME is: given an integer written in binary, return whether it is a prime number or not. A decision problem is equivalent to a language, which is a set of finite-length strings. For a given decision problem, the equivalent language is the set of all strings for which the answer is YES.

Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. For example, the problem HAS-FACTOR is: given integers n and k written in binary, return whether n has any prime factors less than k. If we can solve HAS-FACTOR with a certain amount of resources, then we can use that solution to solve FACTORIZE without much more resources. Just do a binary search on k until you find the smallest factor of n. Then divide out that factor, and repeat until you find all the factors.

Complexity theory often makes a distinction between YES answers and NO answers. For example, the set NP is defined as the set of problems where the YES instances can be checked "quickly" (i.e. in polynomial time). The set Co-NP is the set of problems where the NO instances can be checked quickly. The "Co" in the name stands for "complement". The complement of a problem is one where all the YES and NO answers are swapped, such as IS-COMPOSITE for IS-PRIME.

An important result in complexity theory is the fact that no matter how hard a problem can get (i.e. how much time and space resources it requires), there will always be even harder problems. For time complexity, this is determined by the time hierarchy theorem. A similar space hierarchy theorem can also be derived.

## Схожі: Niweek 2009 Student Design Showcase Submission Form«Theory of automatic control in aerodynamic», «Mechatronic and Robotics», "Theory of mechanic". The presented object of the system... Methods and Applications of Computational Chemistry Computational problems of electrical engineering vol., No., 2012 Computational problems of electrical engineering vol., No., 2012 Centre for Computational Finance and Economic Agents (ccfea) University of Essex, uk Документи1. /PB-MS-theory/Лекции-1(4с.).doc2. /PB-MS-theory/Лекции-2(4с.).doc Документи1. /PB-MS-theory/Лекции-1(4с.).doc2. /PB-MS-theory/Лекции-2(4с.).doc Computational problems of electrical engineering vol., No., 2012Адреса електронної пошти (шрифт Times New Roman, кегль 10, інтервал 1,1; стиль Місце праці) Course Title: Theory and History of English Contents Theory and Methodology of Teaching in High School
Додайте кнопку на своєму сайті:
Документи

База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації