Computational complexity theory
Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, 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, i.e. the amount of resources needed to solve them, such as time and storage. Other measures of complexity are used, such as the amount of communication, the number of gates in a circuit and the number of processors. 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 Millennium Prize Problems, is dedicated to the field of computational complexity.
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 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. 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, 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 and the solution is "yes" if the number is prime and "no" otherwise. Stated another way, the instance is a particular input to the problem, 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 Germany's 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 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.
When considering computational problems, a problem instance is a string over an alphabet. The alphabet is taken to be the binary alphabet, thus the strings are bitstrings; as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary. Though some proofs of complexity-theoretic theorems 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 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, the non-members 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; the formal language associated with this decision problem is 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. A function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include 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 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 such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving
Ronald Fagin is an American mathematician and computer scientist, IBM Fellow at the IBM Almaden Research Center. He is known for his work in database theory, finite model theory, reasoning about knowledge. Ron Fagin grew up in Oklahoma City, where he attended Northwest Classen High School. Following that, he completed his undergraduate degree at Dartmouth College. Fagin received his Ph. D. in Mathematics from the University of California, Berkeley in 1973, where he worked under the supervision of Robert Vaught. He joined the IBM Research Division in 1973, spending two years at the Thomas J. Watson Research Center, transferred in 1975 to what is now the IBM Almaden Research Center in San Jose, California, he has served as program committee chair for ACM Symposium on Principles of Database Systems 1984, Theoretical Aspects of Reasoning about Knowledge 1994, ACM Symposium on Theory of Computing 2005, the International Conference on Database Theory 2009. Fagin has received numerous professional awards for his work.
He was elected Member of the National Academy of Engineering, American Academy of Arts and Sciences, IBM Fellow, ACM Fellow, IEEE Fellow, Fellow of the American Association for the Advancement of Science. He won the 2014 Gödel Prize and he received a Docteur Honoris Causa from the University of Paris; the IEEE granted him the IEEE Technical Achievement Award. Fagin is listed among the "Highly Cited Researchers." He won Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, the 2010 International Conference on Database Theory, the 2015 International Conference on Database Theory. He won 10-year Test-of-Time Awards at the 2011 ACM Symposium on Principles of Database Systems, the 2013 International Conference on Database Theory, the 2014 ACM Symposium on Principles of Database Systems. Fagin's theorem, which he proved in his PhD thesis, states that existential second-order logic coincides with the complexity class NP in the sense that a decision problem can be expressed in existential second-order logic if and only if it can be solved by a non-deterministic Turing machine in polynomial time.
This work helped. Another result that he proved in his PhD thesis is that first-order logic has a zero-one law, a tool for proving inexpressibility results for database query languages; this result was proved independently by Glebskiĭ et al. earlier in Russia, with a different proof. He is known for his work on higher Normal Forms in Database Theory 4NF. Besides Fagin's Theorem, other concepts named after Fagin are "Fagin's algorithm" for score aggregation, the "Fagin-inverse" for data exchange, "Fagin games" and "Ajtai Fagin games" for proving inexpressibility results in logic. Fagin has authored or co-authored numerous articles, a book: Fagin, Joseph Y. Halpern, Yoram Moses, Moshe Y. Vardi. Reasoning about knowledge. MIT press. Paperback edition. Articles, a selection: Fagin, Ronald. "Generalized first-order spectra and polynomial-time recognizable sets". Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings, Vol. Vol. 7:43-73. Fagin, Jurg Nievergelt, Nicholas J. Pippenger, H. Raymond Strong.
"Extendible hashing—a fast access method for dynamic files." ACM Transactions on Database Systems 4.3: 315-344. Fagin, Amnon Lotem, Moni Naor. "Optimal aggregation algorithms for middleware." Journal of Computer and System Sciences 66: 614-656.. Fagin, Phokion Kolaitis, Renee J Miller, Lucian Popa. Data exchange: semantics and query answering, Theoretical Computer Science 336: 89-124.. Ronald Fagin's Website at IBM
Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst. He is one of the key developers of descriptive complexity, an approach he is applying to research in model checking, database theory, computational complexity theory. Professor Immerman is an editor of the SIAM Journal on Computing and of Logical Methods in Computer Science, he received B. S. and M. S. degrees from Yale University in 1974 and his Ph. D. from Cornell University in 1980 under the supervision of Juris Hartmanis, a Turing award winner at Cornell. His book "Descriptive Complexity" appeared in 1999. Immerman is the winner, jointly with Róbert Szelepcsényi, of the 1995 Gödel Prize in theoretical computer science for proof of what is known as the Immerman–Szelepcsényi theorem, the result that nondeterministic space complexity classes are closed under complementation. Immerman is an ACM Fellow and a Guggenheim Fellow. Immerman's home page at U. Mass. Amherst
Moshe Ya'akov Vardi is an Israeli mathematician and computer scientist. He is a Professor of Computer Science at United States, he is the Karen Ostrum George Professor in Computational Engineering, Distinguished Service Professor, Director of the Ken Kennedy Institute for Information Technology. His interests focus on applications of logic to computer science, including database theory, finite-model theory, knowledge in multi-agent systems, computer-aided verification and reasoning, teaching logic across the curriculum, he is an expert in model checking, constraint satisfaction and database theory, common knowledge, theoretical computer science. Moshe Y. Vardi is the author of over 400 technical papers as well as the editor of several collections, he has authored the books Reasoning About Knowledge with Ronald Fagin, Joseph Halpern, Yoram Moses, Finite Model Theory and Its Applications with Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Yde Venema, Scott Weinstein.
He is a former editor-in-chief of Communications of the ACM. He chaired the Computer Science Department at Rice University from January 1994 until June 2002. Prior to joining Rice in 1993, he was at the IBM Almaden Research Center, where he managed the Mathematics and Related Computer Science Department. Dr Vardi received his Ph. D. from the Hebrew University of Jerusalem in 1981. Vardi is the recipient of three IBM Outstanding Innovation Awards, a co-winner of the 2000 Gödel Prize, a co-winner of the 2005 ACM Paris Kanellakis Theory and Practice Award, a co-winner of the LICS 2006 Test-of-Time Award, he is the recipient of the 2008 ACM Presidential Award, the 2008 Blaise Pascal Medal in computational science by the European Academy of Sciences, the 2010 Distinguished Service Award from the Computing Research Association, the Institute of Electrical and Electronics Engineers Computer Society's 2011 Harry H. Goode Memorial Award, he holds honorary doctorates from Saarland University and the University of Orleans, France.
Dr Vardi is an editor of several international journals and the president of the International Federation of Computational Logicians. He is a Guggenheim Fellow, as well as a Fellow of the Association for Computing Machinery, the American Association for the Advancement of Science, the American Association for Artificial Intelligence, he was designated Highly Cited Researcher by the Institute for Scientific Information, was elected as a member of the US National Academy of Engineering, the National Academy of Sciences, the European Academy of Sciences, the Academia Europaea. He was named to the American Academy of Arts and Sciences in 2010, he was included in the 2019 class of fellows of the American Mathematical Society "for contributions to the development and use of mathematical logic in computer science". He has co-chaired the ACM Task Force on Job Migration