146 relations: ACM SIGACT, Advanced Encryption Standard, AKS primality test, Alexander Razborov, Algorithm, Anil Nerode, Annals of Mathematics, Artificial intelligence, Association for Computing Machinery, Average-case complexity, Avi Wigderson, Aviezri Fraenkel, Big O notation, Bonnie Berger, Boolean satisfiability problem, Certificate (complexity), Chess, Clay Mathematics Institute, Co-NP, Co-NP-complete, Cobham's thesis, Complexity class, Composite number, Computational complexity theory, Computer programming, Computer science, Constructive proof, Cook–Levin theorem, Cornell University, Cryptographic hash function, David Eppstein, Decision problem, Descriptive complexity theory, Deterministic automaton, Discrete logarithm, Donald Knuth, Economics, Entscheidungsproblem, Eugene M. Luks, EXPTIME, F. Thomson Leighton, Fermat's Last Theorem, First-order logic, Fixed-point combinator, Game complexity, Game theory, General number field sieve, Gerhard J. Woeginger, Graph (discrete mathematics), Graph isomorphism, ..., Graph isomorphism problem, Halting problem, HP Labs, Independence (mathematical logic), Information-theoretic security, Integer factorization, Integer programming, Introduction to Algorithms, IP (complexity), John Forbes Nash Jr., John Markoff, John von Neumann, Journal of Combinatorial Theory, Journal of the Operational Research Society, Karp's 21 NP-complete problems, Knapsack problem, Kurt Gödel, Lance Fortnow, Latin square, László Babai, Leonid Levin, Linear programming, List of NP-complete problems, List of unsolved problems in computer science, List of unsolved problems in mathematics, Martin Grötschel, Massachusetts Institute of Technology, Michael O. Rabin, Millennium Prize Problems, MIT Press, Moshe Vardi, Multipartite graph, National Security Agency, Natural proof, Neil Immerman, Non-deterministic Turing machine, NP (complexity), NP-completeness, NP-hardness, One-way function, Operations research, Oracle machine, P (complexity), Peano axioms, Pearson Education, PH (complexity), Philosophy, Polymath Project, Polynomial, Polynomial hierarchy, Polynomial-time reduction, Presburger arithmetic, Princeton University, Protein structure prediction, PSPACE, Public-key cryptography, Quantum algorithm, Quantum computing, Randomized algorithm, Reduction (complexity), Rice University, Richard Lipton, Robert M. Solovay, RSA (cryptosystem), Russell Impagliazzo, Scott Aaronson, Second-order logic, Sharp-P-complete, Shor's algorithm, SIAM Journal on Computing, Signature (logic), Simplex algorithm, Stephen Cook, Steven Rudich, String (computer science), Subset sum problem, Sudoku, Symmetric-key algorithm, Symposium on Theoretical Aspects of Computer Science, The New Yorker, The Simpsons, Theoretical computer science, Theory of computation, Time complexity, Time hierarchy theorem, Total order, Travelling Salesman (2012 film), Travelling salesman problem, Treehouse of Horror VI, Triple DES, Turing machine, Undecidable problem, Unique games conjecture, Universal quantification, W. H. Freeman and Company, Zermelo–Fraenkel set theory. Expand index (96 more) » « Shrink index
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science.
The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P".
Aleksandr Aleksandrovich Razborov (Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
Anil Nerode (born 1932) is an American mathematician.
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study.
Artificial intelligence (AI, also machine intelligence, MI) is intelligence demonstrated by machines, in contrast to the natural intelligence (NI) displayed by humans and other animals.
The Association for Computing Machinery (ACM) is an international learned society for computing.
In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.
Avi Wigderson (אבי ויגדרזון; born 9 September 1956) is an Israeli mathematician and computer scientist.
Aviezri Siegmund Fraenkel (אביעזרי פרנקל) (born June 7, 1929) is an Israeli mathematician who has made notable contributions to combinatorial game theory.
Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
Bonnie Anne Berger is an American mathematician and computer scientist, who works as the Simons professor of mathematics and professor of electrical engineering and computer science at the Massachusetts Institute of Technology.
In computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.
In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language.
Chess is a two-player strategy board game played on a chessboard, a checkered gameboard with 64 squares arranged in an 8×8 grid.
The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Peterborough, New Hampshire, United States.
In computational complexity theory, co-NP is a complexity class.
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead.
Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P (PTIME).
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers.
Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
Computer programming is the process of building and designing an executable computer program for accomplishing a specific computing task.
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object.
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.
Cornell University is a private and statutory Ivy League research university located in Ithaca, New York.
A cryptographic hash function is a special class of hash function that has certain properties which make it suitable for use in cryptography.
David Arthur Eppstein (born 1963) is an American computer scientist and mathematician.
In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.
In computer science, a deterministic automaton is a concept of automata theory in which the outcome of a transition from one state to another is determined by the input.
In the mathematics of the real numbers, the logarithm logb a is a number x such that, for given numbers a and b. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that.
Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.
Economics is the social science that studies the production, distribution, and consumption of goods and services.
In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.
Eugene Michael Luks (born circa 1940) is an American mathematician and computer scientist, a professor emeritus of computer and information science at the University of Oregon.
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that have exponential runtime, i.e., that are solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.
Frank Thomson "Tom" Leighton (born 1956) is the CEO of Akamai Technologies, the company he co-founded with Daniel Lewin in 1998.
In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers,, and satisfy the equation for any integer value of greater than 2.
First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.
In computer science's combinatory logic, a fixed-point combinator (or fixpoint combinator) is a higher-order function fix that, for any function f that has an attractive fixed point, returns a fixed point x of that function.
Combinatorial game theory has several ways of measuring game complexity.
Game theory is "the study of mathematical models of conflict and cooperation between intelligent rational decision-makers".
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than.
Gerhard J. Woeginger is an Austrian mathematician and computer scientist who works in Germany as a professor at RWTH Aachen University, where he chairs the algorithms and complexity group in the department of computer science.
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.
HP Labs is the exploratory and advanced research group for HP Inc. HP headquarters is in Palo Alto, California and has research and development facilities in Bristol, UK.
In mathematical logic, independence refers to the unprovability of a sentence from other sentences.
Information-theoretic security is a cryptosystem whose security derives purely from information theory.
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers.
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
In computational complexity theory, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system.
John Forbes Nash Jr. (June 13, 1928 – May 23, 2015) was an American mathematician who made fundamental contributions to game theory, differential geometry, and the study of partial differential equations.
John Gregory Markoff (born October 29, 1949) is a journalist best known for his work at The New York Times, and a book and series of articles about the 1990s pursuit and capture of hacker Kevin Mitnick.
John von Neumann (Neumann János Lajos,; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, and polymath.
The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas.
The Journal of the Operational Research Society is a peer-reviewed academic journal covering operations research.
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete.
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.
Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems.
In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column.
László "Laci" Babai (born July 20, 1950 in Budapest) from Babai's web site, retrieved 2016-01-28.
Leonid Anatolievich Levin (Леони́д Анато́льевич Ле́вин; Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems.
This article is a list of unsolved problems in computer science.
Since the Renaissance, every century has seen the solution of more mathematical problems than the century before, and yet many mathematical problems, both major and minor, still remain unsolved.
Martin Grötschel (born 10 September 1948) is a German mathematician known for his research on combinatorial optimization, polyhedral combinatorics, and operations research.
The Massachusetts Institute of Technology (MIT) is a private research university located in Cambridge, Massachusetts, United States.
Michael Oser Rabin (מִיכָאֵל עוזר רַבִּין, born September 1, 1931) is an Israeli computer scientist and a recipient of the Turing Award.
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000.
The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States).
Moshe Ya'akov Vardi (משה יעקב ורדי) is an Israeli mathematician and computer scientist.
In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are or can be partitioned into k different independent sets.
The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence.
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one.
Neil Immerman (24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.
In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input.
Operations research, or operational research in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions.
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano.
Pearson Education (see also Pearson PLC) is a British-owned education publishing and assessment service to schools and corporations, as well as directly to students.
In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH was first defined by Larry Stockmeyer.
Philosophy (from Greek φιλοσοφία, philosophia, literally "love of wisdom") is the study of general and fundamental problems concerning matters such as existence, knowledge, values, reason, mind, and language.
The Polymath Project is a collaboration among mathematicians to solve important and difficult mathematical problems by coordinating many mathematicians to communicate with each other on finding the best route to the solution.
In mathematics, a polynomial is an expression consisting of variables (also called indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables.
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.
In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine.
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929.
Princeton University is a private Ivy League research university in Princeton, New Jersey.
Protein structure prediction is the inference of the three-dimensional structure of a protein from its amino acid sequence—that is, the prediction of its folding and its secondary and tertiary structure from its primary structure.
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Public-key cryptography, or asymmetric cryptography, is any cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation.
Quantum computing is computing using quantum-mechanical phenomena, such as superposition and entanglement.
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.
William Marsh Rice University, commonly known as Rice University, is a private research university located on a 300-acre (121 ha) campus in Houston, Texas, United States.
Richard Jay Lipton (born September 6, 1946) is an American-British computer scientist who has worked in computer science theory, cryptography, and DNA computing.
Robert Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory.
RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission.
Russell Impagliazzo is a professor of computer science at the University of California, San Diego.
Scott Joel Aaronson (born May 21, 1981) is an American theoretical computer scientist and David J. Bruton Jr.
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.
#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory.
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994.
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science.
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language.
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
Stephen Arthur Cook, (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity.
Steven Rudich (born October 4, 1961) is a professor in the Carnegie Mellon School of Computer Science.
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.
In computer science, the subset sum problem is an important problem in complexity theory and cryptography.
(originally called Number Place) is a logic-based, combinatorial number-placement puzzle.
Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext.
Symposium on Theoretical Aspects of Computer Science (STACS) is an academic conference in the field of computer science.
The New Yorker is an American magazine of reportage, commentary, criticism, essays, fiction, satire, cartoons, and poetry.
The Simpsons is an American animated sitcom created by Matt Groening for the Fox Broadcasting Company.
Theoretical computer science, or TCS, is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation.
In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.
In mathematics, a linear order, total order, simple order, or (non-strict) ordering is a binary relation on some set X, which is antisymmetric, transitive, and a connex relation.
Travelling Salesman is a 2012 intellectual thriller film about four mathematicians solving the P versus NP problem, one of the most challenging mathematical problems in history.
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
"Treehouse of Horror VI" is the sixth episode of The Simpsons' seventh season and the sixth episode in the Treehouse of Horror series.
In cryptography, Triple DES (3DES), officially the Triple Data Encryption Algorithm (TDEA or Triple DEA), is a symmetric-key block cipher, which applies the DES cipher algorithm three times to each data block.
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.
In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002.
In predicate logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all".
In mathematics, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox.
Algebrization, Complexity classes P and NP, NP = P, NP conjecture, NP problem, NP versus P problem, NP=P, NP=P problem, P = NP, P = NP problem, P = NP?, P = np, P ? NP, P Versus NP, P Versus NP Problem, P and NP, P conjecture, P is not NP, P v NP, P versus NP, P vs NP, P vs NP problem, P vs np, P vs. NP, P vs. NP problem, P ≟ NP, P ≠ NP, P!=NP, P/=NP, P/NP Problem, P==NP, P=?NP, P=NP, P=NP problem, P=NP?, P=np, P≟NP, P≠NP, Smale's third problem, Succinct problem, Succinct problems, Vinay Deolalikar, Vinay Deolilakar.