# Theoretical computer science

theoretical computer scientisttheoreticalcomputer sciencecomputer science theoryProgrammingtheoretical models of computationtheoretical onetheoretical perspectiveTheory of Computation
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation.wikipedia
654 Related Articles

### Theory of computation

computational theoristcomputational theorycomputation theory
of computing and includes the theory of computation. Computational complexity theory is a branch of the theory of computation that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
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.

### Mathematical logic

formal logicsymbolic logiclogic
It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science.

### Automata theory

automataautomatonautomata theories
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them.
It is a theory in theoretical computer science and discrete mathematics (a subject of study in both mathematics and computer science).

### Combinatorial optimization

combinatorial optimisationcombinatorial searchcombinatorial
In operations research, applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects.

### Automated reasoning

reasoningArtificial intelligence reasoningautomated inferencing
Algorithms are used for calculation, data processing, and automated reasoning.
Although automated reasoning is considered a sub-field of artificial intelligence, it also has connections with theoretical computer science, and even philosophy.

### Category theory

categorycategoricalcategories
Categories now appear in many branches of mathematics, some areas of theoretical computer science where they can correspond to types or to database schemas, and mathematical physics where they can be used to describe vector spaces.

### Computational problem

computational problemsproblemdecision problem
Computational complexity theory is a branch of the theory of computation that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

### Discrete mathematics

discretediscrete mathdiscrete structure
It is a theory in theoretical computer science, under Discrete mathematics (a section of Mathematics and also of Computer Science).
The need to break German codes in World War II led to advances in cryptography and theoretical computer science, with the first programmable digital electronic computer being developed at England's Bletchley Park with the guidance of Alan Turing and his seminal work, On Computable Numbers.

### Communication complexity

Other complexity measures 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).
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties.

### Circuit complexity

non-uniformcircuitmonotone circuit
Other complexity measures 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).
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them.

### Mathematics

mathematicalmathmathematician
It is a theory in theoretical computer science, under Discrete mathematics (a section of Mathematics and also of Computer Science). Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on more mathematical topics Formal methods are a particular kind of mathematics based techniques for the specification, development and verification of software and hardware systems.
Modern logic is divided into recursion theory, model theory, and proof theory, and is closely linked to theoretical computer science, as well as to category theory.

### Applied mathematics

applied mathematicianappliedapplications of mathematics
The field is broadly defined and includes foundations in computer science, applied mathematics, animation, statistics, biochemistry, chemistry, biophysics, molecular biology, genetics, genomics, ecology, evolution, anatomy, neuroscience, and visualization.
The advent of the computer has enabled new applications: studying and using the new computer technology itself (computer science) to study problems arising in other areas of science (computational science) as well as the mathematics of computation (for example, theoretical computer science, computer algebra, numerical analysis).

### Formal methods

formal methodformalformal analysis
Formal methods are a particular kind of mathematics based techniques for the specification, development and verification of software and hardware systems.
Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular logic calculi, formal languages, automata theory, discrete event dynamic system and program semantics, but also type systems and algebraic data types to problems in software and hardware specification and verification.

### NP-completeness

NP-completeNP completeNP-complete problem
In 1971, Stephen Cook and, working independently, Leonid Levin, proved that there exist practically relevant problems that are NP-complete – a landmark result in computational complexity theory.
He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the theoretical computer science community.

### Computer science

computer scientistcomputer sciencescomputer scientists
It is a theory in theoretical computer science, under Discrete mathematics (a section of Mathematics and also of Computer Science). Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on more mathematical topics
Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular logic calculi, formal languages, automata theory, and program semantics, but also type systems and algebraic data types to problems in software and hardware specification and verification.

### Machine learning

machine-learninglearningstatistical learning
Machine learning is a scientific discipline that deals with the construction and study of algorithms that can learn from data.
The computational analysis of machine learning algorithms and their performance is a branch of theoretical computer science known as computational learning theory.

### String (computer science)

stringstringscharacter string
It does so by evaluating the meaning of syntactically legal strings defined by a specific programming language, showing the computation involved.
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set called an alphabet.

### Distributed computing

distributeddistributed systemsdistributed system
Distributed computing studies distributed systems.
In theoretical computer science, such tasks are called computational problems.

### Computational science

scientific computingscientific computationcomputational
Although, properly speaking, computer algebra should be a subfield of scientific computing, they are generally considered as distinct fields because scientific computing is usually based on numerical computation with approximate floating point numbers, while symbolic computation emphasizes exact computation with expressions containing variables that have not any given value and are thus manipulated as symbols (therefore the name of symbolic computation).

### Nondeterministic Turing machine

non-deterministic Turing machinenondeterministicnon-deterministic
Quantum computers share theoretical similarities with non-deterministic and probabilistic computers; one example is the ability to be in more than one state simultaneously.
In theoretical computer science, a nondeterministic Turing machine is a theoretical model of computation.

### European Association for Theoretical Computer Science

EATCSEATCS AwardBulletin of the EATCS

### Symposium on Theory of Computing

STOCACM Symposium on Theory of ComputingDanny Lewin Best Student Paper Award
The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science.

### ACM SIGACT

SIGACTSIGACT NewsACM Special Interest Group on Algorithms and Computability Theory
The ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description:
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.

### Simons Institute for the Theory of Computing

Simons Institute
The Simons Institute for the Theory of Computing at the University of California, Berkeley is a venue for collaborative research in theoretical computer science.

### List of important publications in theoretical computer science

On Computable NumbersImportant publications in algorithmic information theoryImportant publications in computability
This is a list of important publications in theoretical computer science, organized by field.