软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
计算复杂性(Computing Complexity)

作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站

Computational complexity theory
From Wikipedia, the free encyclopedia.
Printable version | Pages that link here
12.234.196.121
Log in | Help
 

[Main Page]
Main Page | Recent Changes | Edit this page | History | Random Page | Special Pages
Complexity Theory is a part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.

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, as a function of the size of the instance. If an instance that is n bits long can be solved in n2 steps, then we say it has a time complexity of n2. 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(n2) on one typical computer, then it will also have complexity O(n2) on most other computers, so this notation allows us to generalize away from the details of a particular computer.

 

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. 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.

 

 

The P=NP Question

The set P is the set of decision problems that can be solved in polynomial time. The question of whether P is the same set as NP is the most important open question in theoretical computer science. There is even a $1,000,000 prize for solving it. (See Complexity classes P and NP and oracles).

Questions like this motivate the concepts of hard and complete. A set of problems X is hard for a set of problems Y if every problem in Y can be transformed easily into some problem in X with the same answer. The definition of "easily" is different in different contexts. The most important hard set is NP-hard. Set X is complete for Y if it is hard for Y, and is also a subset of Y. The most important complete set is NP-complete. See the articles on those two sets for more detail on the definition of "hard" and "complete".

 

Famous Complexity Classes

The following are some of the classes of problems considered in complexity theory, along with rough definitions. See computation for a chart showing which classes are subsets of other classes.

 

P   Solvable in polynomial time (see Complexity classes P and NP)
NP   YES answers checkable in polynomial time (see Complexity classes P and NP)
Co-NP   NO answers checkable in polynomial time
NP-complete   The hardest problems in NP
Co-NP-complete   The hardest problems in Co-NP
NP-hard   Either NP-complete or harder
NP-easy   non-decision-problem analogue to NP
NP-equivalent   non-decision-problem analogue to NP-complete
#P   Count solutions to an NP problem
#P-complete   The hardest problems in #P
NC   Solvable efficiently on parallel computers
P-complete   The hardest problems in P to solve on parallel computers
PSPACE   Solvable with polynomial memory and unlimited time
PSPACE-complete   The hardest problems in PSPACE
EXPTIME   Solvable with exponential time
EXPSPACE   Solvable with exponential memory and unlimited time
BQP   Solvable in polynomial time on a quantum computer (answer is probably right)
BPP   Solvable in polynomial time by randomized algorithms (answer is probably right)
RP   Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
ZPP   Solvable by randomized algorithms (answer is always right, average running time is polynomial)

 

Main Page
Recent Changes
Watch page links
Edit this page
History
Upload files

Statistics
New pages
Orphans
Most wanted
Most popular
Random Page
Stub articles
Long articles
List users
Bug reports
June 23, 2002


Talk

This page has been accessed 2248 times. Other namespaces : Talk
Last edited: Sunday, June 2, 2002, 13:50 (diff)

    Validate this page




相关文章

相关软件