computational complexity theory computer science theory that classifies problems according to their inherent difficulty computational complexity theory focuses on classifying computational problems according to their inherent difficulty and relating these classes to each other a computational problem is a task solved by a computer a computation problem is solvable by mechanical application of mathematical steps such as an algorithm a problem is regarded as inherently difficult if its solution requires significant resources whatever the algorithm used the theory formalizes this intuition by introducing mathematical models of computation to study these problems and quantifying their computational complexity ie the amount of resources needed to solve them such as time and storage other measures of complexity are also used such as the amount of communication used in communication complexity the number of gates in a circuit used in circuit complexity and the number of processors used in parallel computing one of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do the p versus np problem one of the seven millenium prize problems is dedicated to the field of computational complexity closely related fields in theoretical computer science are analysis of algorithms and computability theory a key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem more precisely computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources in turn imposing restrictions on the available resources is what distinguishes computational complexity from computability theory the latter theory asks what kind of problems can in principle be solved algorithmically computational problems a traveling salesman tour through germanys 15 largest cities problem instances a computational problem can be viewed as an infinite collection of instances together with a solution for every instance the input string for a computational problem is referred to as a problem instance and should not be confused with the problem itself in computational complexity theory a problem refers to the abstract question to be solved in contrast an instance of this problem is a rather concrete utterance which can serve as the input for a decision problem for example consider the problem of primality testing the instance is a number eg 15 and the solution is yes if the number is prime and no otherwise in this case 15 is not prime and the answer is no stated another way the instance is a particular input to the problem and the solution is the output corresponding to the given input to further highlight the difference between a problem and an instance consider the following instance of the decision version of the traveling salesman problem is there a route of at most 2000 kilometres passing through all of germanys 15 largest cities the quantitative answer to this particular problem instance is of little use for solving other instances of the problem such as asking for a round trip through all sites in milan whose total length is at most 10km for this reason complexity theory addresses computational problems and not particular problem instances representing problem instances when considering computational problems a problem instance is a string over an alphabet usually the alphabet is taken to be the binary alphabet ie the set 01 and thus the strings are bitstrings as in a realworld computer mathematical objects other than bitstrings must be suitably encoded for example integers can be represented in binary notation and graphs can be encoded directly via their adjacency matrices or by encoding their adjacency lists in binary even though some proofs of complexitytheoretic theorems regularly assume some concrete choice of input encoding one tries to keep the discussion abstract enough to be independent of the choice of encoding this can be achieved by ensuring that different representations can be transformed into each other efficiently decision problems as formal languages a decision problem has only two possible outputs yes or no or alternately 1 or 0 on any input decision problems are one of the central objects of study in computational complexity theory a decision problem is a special type of computational problem whose answer is either yes or no or alternately either 1 or 0 a decision problem can be viewed as a formal language where the members of the language are instances whose output is yes and the nonmembers are those instances whose output is no the objective is to decide with the aid of an algorithm whether a given input string is a member of the formal language under consideration if the algorithm deciding this problem returns the answer yes the algorithm is said to accept the input string otherwise it is said to reject the input an example of a decision problem is the following the input is an arbitrary graph the problem consists in deciding whether the given graph is connected or not the formal language associated with this decision problem is then the set of all connected graphs to obtain a precise definition of this language one has to decide how graphs are encoded as binary strings function problems a function problem is a computational problem where a single output of a total function is expected for every input but the output is more complex than that of a decision problemthat is the output isnt just yes or no notable examples include the traveling salesman problem and the integer factorization problem it is tempting to think that the notion of function problems is much richer than the notion of decision problems however this is not really the case since function problems can be recast as decision problems for example the multiplication of two integers can be expressed as the set of triples abc such that the relation abc holds deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers measuring the size of an instance to measure the difficulty of solving a computational problem one may wish to see how much time the best algorithm requires to solve the problem however the running time may in general depend on the instance in particular larger instances will require more time to solve thus the time required to solve a problem or the space required or any measure of complexity is calculated as a function of the size of the instance this is usually taken to be the size of the input in bits complexity theory is interested in how algorithms scale with an increase in the input size for instance in the problem of finding whether a graph is connected how much more time does it take to solve a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices if the input size is n the time taken can be expressed as a function of n since the time taken on different inputs of the same size can be different the worstcase time complexity tn is defined to be the maximum time taken over all inputs of size n if tn is a polynomial in n then the algorithm is said to be a polynomial time algorithm cobhams thesis argues that a problem can be solved with a feasible amount of resources if it admits a polynomial time algorithm machine models and complexity measures turing machine an illustration of a turing machine turing machine a turing machine is a mathematical model of a general computing machine it is a theoretical device that manipulates symbols contained on a strip of tape turing machines are not intended as a practical computing technology but rather as a general model of a computing machineanything from an advanced supercomputer to a mathematician with a pencil and paper it is believed that if a problem can be solved by an algorithm there exists a turing machine that solves the problem indeed this is the statement of the churchturing thesis furthermore it is known that everything that can be computed on other models of computation known to us today such as a ram machine conways game of life cellular automata or any programming language can be computed on a turing machine since turing machines are easy to analyze mathematically and are believed to be as powerful as any other model of computation the turing machine is the most commonly used model in complexity theory many types of turing machines are used to define complexity classes such as deterministic turing machines probabilistic turing machines nondeterministic turing machines quantum turing machines symmetric turing machines and alternating turing machines they are all equally powerful in principle but when resources such as time or space are bounded some of these may be more powerful than others a deterministic turing machine is the most basic turing machine which uses a fixed set of rules to determine its future actions a probabilistic turing machine is a deterministic turing machine with an extra supply of random bits the ability to make probabilistic decisions often helps algorithms solve problems more efficiently algorithms that use random bits are called randomized algorithms a nondeterministic turing machine is a deterministic turing machine with an added feature of nondeterminism which allows a turing machine to have multiple possible future actions from a given state one way to view nondeterminism is that the turing machine branches into many possible computational paths at each step and if it solves the problem in any of these branches it is said to have solved the problem clearly this model is not meant to be a physically realizable model it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes for examples see nondeterministic algorithm other machine models many machine models different from the standard multitape turing machines have been proposed in the literature for example random access machines perhaps surprisingly each of these models can be converted to another without providing any extra computational power the time and memory consumption of these alternate models may vary what all these models have in common is that the machines operate deterministically however some computational problems are easier to analyze in terms of more unusual resources for example a nondeterministic turing machine is a computational model that is allowed to branch out to check many different possibilities at once the nondeterministic turing machine has very little to do with how we physically want to compute algorithms but its branching exactly captures many of the mathematical models we want to analyze so that nondeterministic time is a very important resource in analyzing computational problems complexity measures for a precise definition of what it means to solve a problem using a given amount of time and space a computational model such as the deterministic turing machine is used the time required by a deterministic turing machine m on input x is the total number of state transitions or steps the machine makes before it halts and outputs the answer yes or no a turing machine m is said to operate within time fn if the time required by m on each input of length n is at most fn a decision problem a can be solved in time fn if there exists a turing machine operating in time fn that solves the problem since complexity theory is interested in classifying problems based on their difficulty one defines sets of problems based on some criteria for instance the set of problems solvable within time fn on a deterministic turing machine is then denoted by dtimefn analogous definitions can be made for space requirements although time and space are the most wellknown complexity resources any complexity measure can be viewed as a computational resource complexity measures are very generally defined by the blum complexity axioms other complexity measures used in complexity theory include communication complexity circuit complexity and decision tree complexity the complexity of an algorithm is often expressed using big o notation best worst and average case complexity visualization of the quicksort algorithm that has average case performance o n log n displaystyle mathcal onlog n the best worst and average case complexity refer to three different ways of measuring the time complexity or any other complexity measure of different inputs of the same size since some inputs of size n may be faster to solve than others we define the following complexities bestcase complexity this is the complexity of solving the problem for the best input of size n worstcase complexity this is the complexity of solving the problem for the worst input of size n averagecase complexity this is the complexity of solving the problem on an average this complexity is only defined with respect to a probability distribution over the inputs for instance if all inputs of the same size are assumed to be equally likely to appear the average case complexity can be defined with respect to the uniform distribution over all inputs of size n for example consider the deterministic sorting algorithm quicksort this solves the problem of sorting a list of integers that is given as the input the worstcase is when the input is sorted or sorted in reverse order and the algorithm takes time on2 for this case if we assume that all possible permutations of the input list are equally likely the average time taken for sorting is on log n the best case occurs when each pivoting divides the list in half also needing on log n time upper and lower bounds on the complexity of problems to classify the computation time or similar resources such as space consumption one is interested in proving upper and lower bounds on the maximum amount of time required by the most efficient algorithm solving a given problem the complexity of an algorithm is usually taken to be its worstcase complexity unless specified otherwise analyzing a particular algorithm falls under the field of analysis of algorithms to show an upper bound tn on the time complexity of a problem one needs to show only that there is a particular algorithm with running time at most tn however proving lower bounds is much more difficult since lower bounds make a statement about all possible algorithms that solve a given problem the phrase all possible algorithms includes not just the algorithms known today but any algorithm that might be discovered in the future to show a lower bound of tn for a problem requires showing that no algorithm can have time complexity lower than tn upper and lower bounds are usually stated using the big o notation which hides constant factors and smaller terms this makes the bounds independent of the specific details of the computational model used for instance if tn7n215n40 in big o notation one would write tnon2 complexity classes complexity class defining complexity classes a complexity class is a set of problems of related complexity simpler complexity classes are defined by the following factors the type of computational problem the most commonly used problems are decision problems however complexity classes can be defined based on function problems counting problems optimization problems promise problems etc the model of computation the most common model of computation is the deterministic turing machine but many complexity classes are based on nondeterministic turing machines boolean circuits quantum turing machines monotone circuits etc the resource or resources that are being bounded and the bounds these two properties are usually stated together such as polynomial time logarithmic space constant depth etc some complexity classes have complicated definitions that do not fit into this framework thus a typical complexity class has a definition like the following the set of decision problems solvable by a deterministic turing machine within time fn this complexity class is known as dtimefn but bounding the computation time above by some concrete function fn often yields complexity classes that depend on the chosen machine model for instance the language xx x is any binary string can be solved in linear time on a multitape turing machine but necessarily requires quadratic time in the model of singletape turing machines if we allow polynomial variations in running time cobhamedmonds thesis states that the time complexities in any two reasonable and general models of computation are polynomially related goldreich 2008 chapter 12 this forms the basis for the complexity class p which is the set of decision problems solvable by a deterministic turing machine within polynomial time the corresponding set of function problems is fp important complexity classes a representation of the relation among complexity classes many important complexity classes can be defined by bounding the time or space used by the algorithm some important complexity classes of decision problems defined in this manner are the following complexity class model of computation resource constraint deterministic time dtimefn deterministic turing machine time fn p deterministic turing machine time polyn exptime deterministic turing machine time 2polyn nondeterministic time ntimefn nondeterministic turing machine time fn np nondeterministic turing machine time polyn nexptime nondeterministic turing machine time 2polyn complexity class model of computation resource constraint deterministic space dspacefn deterministic turing machine space fn l deterministic turing machine space olog n pspace deterministic turing machine space polyn expspace deterministic turing machine space 2polyn nondeterministic space nspacefn nondeterministic turing machine space fn nl nondeterministic turing machine space olog n npspace nondeterministic turing machine space polyn nexpspace nondeterministic turing machine space 2polyn the logarithmicspace classes necessarily do not take into account the space needed to represent the problem it turns out that pspace npspace and expspace nexpspace by savitchs theorem other important complexity classes include bpp zpp and rp which are defined using probabilistic turing machines ac and nc which are defined using boolean circuits and bqp and qma which are defined using quantum turing machines p is an important complexity class of counting problems not decision problems classes like ip and am are defined using interactive proof systems all is the class of all decision problems hierarchy theorems time hierarchy theorem and space hierarchy theorem for the complexity classes defined in this way it is desirable to prove that relaxing the requirements on say computation time indeed defines a bigger set of problems in particular although dtimen is contained in dtimen2 it would be interesting to know if the inclusion is strict for time and space requirements the answer to such questions is given by the time and space hierarchy theorems respectively they are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources thus there are pairs of complexity classes such that one is properly included in the other having deduced such proper set inclusions we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved more precisely the time hierarchy theorem states that d t i m e f n d t i m e f n log 2 f n displaystyle mathsf dtimebig fnbig subsetneq mathsf dtimebig fncdot log 2fnbig the space hierarchy theorem states that d s p a c e f n d s p a c e f n log f n displaystyle mathsf dspacebig fnbig subsetneq mathsf dspacebig fncdot logfnbig the time and space hierarchy theorems form the basis for most separation results of complexity classes for instance the time hierarchy theorem tells us that p is strictly contained in exptime and the space hierarchy theorem tells us that l is strictly contained in pspace reduction reduction complexity many complexity classes are defined using the concept of a reduction a reduction is a transformation of one problem into another problem it captures the informal notion of a problem being at most as difficult as another problem for instance if a problem x can be solved using an algorithm for y x is no more difficult than y and we say that x reduces to y there are many different types of reductions based on the method of reduction such as cook reductions karp reductions and levin reductions and the bound on the complexity of reductions such as polynomialtime reductions or logspace reductions the most commonly used reduction is a polynomialtime reduction this means that the reduction process takes polynomial time for example the problem of squaring an integer can be reduced to the problem of multiplying two integers this means an algorithm for multiplying two integers can be used to square an integer indeed this can be done by giving the same input to both inputs of the multiplication algorithm thus we see that squaring is not more difficult than multiplication since squaring can be reduced to multiplication this motivates the concept of a problem being hard for a complexity class a problem x is hard for a class of problems c if every problem in c can be reduced to x thus no problem in c is harder than x since an algorithm for x allows us to solve any problem in c the notion of hard problems depends on the type of reduction being used for complexity classes larger than p polynomialtime reductions are commonly used in particular the set of problems that are hard for np is the set of nphard problems if a problem x is in c and hard for c then x is said to be complete for c this means that x is the hardest problem in c since many problems could be equally hard one might say that x is one of the hardest problems in c thus the class of npcomplete problems contains the most difficult problems in np in the sense that they are the ones most likely not to be in p because the problem pnp is not solved being able to reduce a known npcomplete problem 2 to another problem 1 would indicate that there is no known polynomialtime solution for 1 this is because a polynomialtime solution to 1 would yield a polynomialtime solution to 2 similarly because all np problems can be reduced to the set finding an npcomplete problem that can be solved in polynomial time would mean that pnp important open problems diagram of complexity classes provided that pnp the existence of problems in np outside both p and npcomplete in this case was established by ladner p versus np problem p versus np problem the complexity class p is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm this hypothesis is called the cobhamedmonds thesis the complexity class np on the other hand contains many problems that people would like to solve efficiently but for which no efficient algorithm is known such as the boolean satisfiability problem the hamiltonian path problem and the vertex cover problem since deterministic turing machines are special nondeterministic turing machines it is easily observed that each problem in p is also member of the class np the question of whether p equals np is one of the most important open questions in theoretical computer science because of the wide implications of a solution problems in np not known to be in p or npcomplete it was shown by ladner that if p np then there exist problems in np that are neither in p nor npcomplete such problems are called npintermediate problems the graph isomorphism problem the discrete logarithm problem and the integer factorization problem are examples of problems believed to be npintermediate they are some of the very few np problems not known to be in p or to be npcomplete the graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic an important unsolved problem in complexity theory is whether the graph isomorphism problem is in p npcomplete or npintermediate the answer is not known but it is believed that the problem is at least not npcomplete since it is widely believed that the polynomial hierarchy does not collapse to any finite level it is believed that graph isomorphism is not npcomplete the best algorithm for this problem due to lszl babai and eugene luks has run time o 2 n log n displaystyle o2sqrt nlog n for graphs with n vertices although some recent work by babai offers some potentially new perspectives on this the integer factorization problem is the computational problem of determining the prime factorization of a given integer phrased as a decision problem it is the problem of deciding whether the input has a prime factor less than k no efficient integer factorization algorithm is known and this fact forms the basis of several modern cryptographic systems such as the rsa algorithm the integer factorization problem is in np and in conp and even in up and coup if the problem is npcomplete the polynomial time hierarchy will collapse to its first level ie np will equal conp the best known algorithm for integer factorization is the general number field sieve which takes time o e 64 9 1 3 log n 1 3 log log n 2 3 displaystyle oeleftfrac 649right13log n13log log n23 to factor an integer n however the best known quantum algorithm for this problem shors algorithm does run in polynomial time unfortunately this fact doesnt say much about where the problem lies with respect to nonquantum complexity classes separations between other complexity classes many known complexity classes are suspected to be unequal but this has not been proved for instance p np pp pspace but it is possible that p pspace if p is not equal to np then p is not equal to pspace either since there are many known complexity classes between p and pspace such as rp bpp pp bqp ma ph etc it is possible that all these complexity classes collapse to one class proving that any of these classes are unequal would be a major breakthrough in complexity theory along the same lines conp is the class containing the complement problems ie problems with the yesno answers reversed of np problems it is believed that np is not equal to conp however it has not yet been proven it is clear that if these two complexity classes are not equal then p is not equal to np since if pnp we would also have pconp since problems in np are dual to those in conp similarly it is not known if l the set of all problems that can be solved in logarithmic space is strictly contained in p or equal to p again there are many complexity classes between the two such as nl and nc and it is not known if they are distinct or equal classes it is suspected that p and bpp are equal however it is currently open if bpp nexp intractability see also combinatorial explosion look up tractable feasible intractability or infeasible in wiktionary the free dictionary a problem that can be solved in theory eg given large but finite resources especially time but for which in practice any solution takes too many resources to be useful is known as an intractable problem tractable problems are frequently identified with problems that have polynomialtime solutions p ptime this is known as the cobhamedmonds thesis problems that are known to be intractable in this sense include those that are exptimehard if np is not the same as p then nphard problems are also intractable in this sense however this identification is inexact a polynomialtime solution with large exponent or large constant term grows quickly and may be impractical for practical size problems conversely an exponentialtime solution that grows slowly may be practical on realistic input or a solution that takes a long time in the worst case may take a short time in most cases or the average case and thus still be practical saying that a problem is not in p does not imply that all large cases of the problem are hard or even that most of them are for example the decision problem in presburger arithmetic has been shown not to be in p yet algorithms have been written that solve the problem in reasonable times in most cases similarly algorithms can solve the npcomplete knapsack problem over a wide range of sizes in less than quadratic time and sat solvers routinely handle large instances of the npcomplete boolean satisfiability problem to see why exponentialtime algorithms are generally unusable in practice consider a program that makes 2n operations before halting for small n say 100 and assuming for the sake of example that the computer does 1012 operations each second the program would run for about 41010 years which is the same order of magnitude as the age of the universe even with a much faster computer the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress however an exponentialtime algorithm that takes 10001n operations is practical until n gets relatively large similarly a polynomial time algorithm is not always practical if its running time is say n15 it is unreasonable to consider it efficient and it is still useless except on small instances indeed in practice even n3 or n2 algorithms are often impractical on realistic sizes of problems history an early example of algorithm complexity analysis is the running time analysis of the euclidean algorithm done by gabriel lam in 1844 before the actual research explicitly devoted to the complexity of algorithmic problems started off numerous foundations were laid out by various researchers most influential among these was the definition of turing machines by alan turing in 1936 which turned out to be a very robust and flexible simplification of a computer the beginning of systematic studies in computational complexity is attributed to the seminal 1965 paper on the computational complexity of algorithms by juris hartmanis and richard e stearns which laid out the definitions of time complexity and space complexity and proved the hierarchy theorems earlier papers studying problems solvable by turing machines with specific bounded resources include as he remembers however in 1967 manuel blum formulated a set of axioms now known as blum axioms specifying desirable properties of complexity measures on the set of computable functions and proved an important result the socalled speedup theorem the field began to flourish in 1971 when the stephen cook and leonid levin proved the existence of practically relevant problems that are npcomplete in 1972 richard karp took this idea a leap forward with his landmark paper reducibility among combinatorial problems in which he showed that 21 diverse combinatorial and graph theoretical problems each infamous for its computational intractability are npcomplete in the 1980s much work was done on the average difficulty of solving npcomplete problemsboth exactly and approximately at that time computational complexity theory was at its height and it was widely believed that if a problem turned out to be npcomplete then there was little chance of being able to work with the problem in a practical situation however it became increasingly clear that this is not always the case and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice categorycomputational problems context of computational complexity descriptive complexity theory game complexity list of complexity classes list of computability and complexity topics list of important publications in theoretical computer science list of unsolved problems in computer science parameterized complexity proof complexity quantum complexity theory structural complexity theory transcomputational problem citations textbooks arora sanjeev barak boaz 2009 computational complexity a modern approach cambridge isbn9780521424264 zbl119368112 downey rod fellows michael 1999 parameterized complexity berlin new york springerverlag du dingzhu ko keri 2000 theory of computational complexity john wiley sons isbn9780471345060 garey michael r johnson david s 1979 computers and intractability a guide to the theory of npcompleteness whfreeman isbn0716710455 goldreich oded 2008 computational complexity a conceptual perspective cambridge university press van leeuwen jan ed 1990 handbook of theoretical computer science vol a algorithms and complexity mit press isbn9780444880710 papadimitriou christos 1994 computational complexity 1st ed addison wesley isbn9780201530827 sipser michael 2006 introduction to the theory of computation 2nd ed usa thomson course technology isbn9780534950972 surveys khalil hatem ulery dana 1976 a review of current studies on complexity of algorithms for partial differential equations proceedings of the annual conference on acm 76 197201 doi101145800191805573 cook stephen 1983 an overview of computational complexity pdf commun acm 26 6 400408 doi101145358141358144 issn00010782 fortnow lance homer steven 2003 a short history of computational complexity pdf bulletin of the eatcs 80 95133 mertens stephan 2002 computational complexity for physicists computing in science and eng 4 3 3147 arxivcondmat0012185 doi1011095992998639 issn15219615 wikimedia commons has media related to computational complexity theory the complexity zoo hazewinkel michiel ed 2001 computational complexity classes encyclopedia of mathematics springer sciencebusiness media bv kluwer academic publishers isbn9781556080104 httpmathoverflownetquestions34487whatarethemostimportantresultsandpapersincomplexitytheorythatevery vteimportant complexity classes moreconsidered feasible dlogtime ac0 acc0 tc0 l sl rl nl nc sc cc p pcomplete zpp rp bpp bqp apx suspected infeasible up np npcomplete nphard conp conpcomplete am qma ph p pp p pcomplete ip pspace pspacecomplete considered infeasible exptime nexptime expspace elementary pr r re all class hierarchies polynomial hierarchy exponential hierarchy grzegorczyk hierarchy arithmetical hierarchy boolean hierarchy families of classes dtime ntime dspace nspace probabilistically checkable proof interactive proof system vtemajor fields of computer sciencenote this template roughly follows the 2012 acm computing classification systemhardware printed circuit board peripheral integrated circuit very large scale integration systems on chip socs energy consumption green computing electronic design automation hardware acceleration computer systemsorganization computer architecture embedded system realtime computing dependability networks network architecture network protocol network components network scheduler network performance evaluation network service software organization interpreter middleware virtual machine operating system software quality software notationsand tools programming paradigm programming language compiler domainspecific language modeling language software framework integrated development environment software configuration management software library software repository software development software development process requirements analysis software design software construction software deployment software maintenance programming team opensource model theory of computation model of computation formal language automata theory computational complexity theory logic semantics algorithms algorithm design analysis of algorithms algorithmic efficiency randomized algorithm computational geometry mathematicsof computing discrete mathematics probability statistics mathematical software information theory mathematical analysis numerical analysis informationsystems database management system information storage systems enterprise information system social information systems geographic information system decision support system process control system multimedia information system data mining digital library computing platform digital marketing world wide web information retrieval security cryptography formal methods security services intrusion detection system hardware security network security information security application security humancomputerinteraction interaction design social computing ubiquitous computing visualization accessibility concurrency concurrent computing parallel computing distributed computing multithreading multiprocessing artificialintelligence natural language processing knowledge representation and reasoning computer vision automated planning and scheduling search methodology control method philosophy of artificial intelligence distributed artificial intelligence machine learning supervised learning unsupervised learning reinforcement learning multitask learning crossvalidation graphics animation rendering image manipulation graphics processing unit mixed reality virtual reality image compression solid modeling appliedcomputing ecommerce enterprise software computational mathematics computational physics computational chemistry computational biology computational social science computational engineering computational healthcare digital art electronic publishing cyberwarfare electronic voting video games word processing operations research educational technology document management book category portal wikiproject commons authority control gnd 41205911 