en.unionpedia.org

Decision problem, the Glossary

Index Decision problem

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values.[1]

Table of Contents

  1. 43 relations: Algorithm, ALL (complexity), Alphabet (formal languages), Boolean satisfiability problem, Co-NP-complete, Complement (complexity), Complete (complexity), Complexity class, Computability theory, Computable set, Computably enumerable set, Computational complexity theory, Computational problem, Computational resource, Counting problem (complexity), Decidability (logic), Effective method, Formal language, Function problem, Gödel numbering, Halting problem, Indicator function, Infinite set, Linear programming, List of undecidable problems, Long division, Many-one reduction, NP (complexity), NP-completeness, Operations research, Partial function, Polynomial-time reduction, Primality test, Prime number, Search problem, String (computer science), Theory (mathematical logic), Time complexity, Travelling salesman problem, Turing degree, Undecidable problem, Word problem (mathematics), Yes–no question.

  2. Computational problems

Algorithm

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

See Decision problem and Algorithm

ALL (complexity)

In computability and complexity theory, ALL is the class of all decision problems.

See Decision problem and ALL (complexity)

Alphabet (formal languages)

In formal language theory, an alphabet, sometimes called a vocabulary, is a non-empty set of indivisible symbols/characters/glyphs, typically thought of as representing letters, characters, digits, phonemes, or even words.

See Decision problem and Alphabet (formal languages)

Boolean satisfiability problem

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.

See Decision problem and Boolean satisfiability problem

Co-NP-complete

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.

See Decision problem and Co-NP-complete

Complement (complexity)

In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.

See Decision problem and Complement (complexity)

Complete (complexity)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.

See Decision problem and Complete (complexity)

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity".

See Decision problem and Complexity class

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

See Decision problem and Computability theory

Computable set

In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not. Decision problem and computable set are computability theory.

See Decision problem and Computable set

Computably enumerable set

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if. Decision problem and computably enumerable set are computability theory.

See Decision problem and Computably enumerable set

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other.

See Decision problem and Computational complexity theory

Computational problem

In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. Decision problem and computational problem are computational problems.

See Decision problem and Computational problem

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

See Decision problem and Computational resource

Counting problem (complexity)

In computational complexity theory and computability theory, a counting problem is a type of computational problem. Decision problem and counting problem (complexity) are computational problems.

See Decision problem and Counting problem (complexity)

Decidability (logic)

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer.

See Decision problem and Decidability (logic)

Effective method

In logic, mathematics and computer science, especially metalogic and computability theory, an effective methodHunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971 or effective procedure is a procedure for solving a problem by any intuitively 'effective' means from a specific class. Decision problem and effective method are computability theory.

See Decision problem and Effective method

Formal language

In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules called a formal grammar.

See Decision problem and Formal language

Function problem

In computational complexity theory, 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 problem. Decision problem and function problem are computational problems.

See Decision problem and Function problem

Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number.

See Decision problem and Gödel numbering

Halting problem

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, or continue to run forever. Decision problem and halting problem are computability theory.

See Decision problem and Halting problem

Indicator function

In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero.

See Decision problem and Indicator function

Infinite set

In set theory, an infinite set is a set that is not a finite set.

See Decision problem and Infinite set

Linear programming

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 and objective are represented by linear relationships.

See Decision problem and Linear programming

List of undecidable problems

In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. Decision problem and List of undecidable problems are computability theory.

See Decision problem and List of undecidable problems

Long division

In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu-Arabic numerals (positional notation) that is simple enough to perform by hand.

See Decision problem and Long division

Many-one reduction

In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether an instance is in L_2) using a computable function.

See Decision problem and Many-one reduction

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems.

See Decision problem and NP (complexity)

NP-completeness

In computational complexity theory, a problem is NP-complete when.

See Decision problem and NP-completeness

Operations research

Operations research (operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decision-making.

See Decision problem and Operations research

Partial function

In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to.

See Decision problem and Partial function

Polynomial-time reduction

In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another.

See Decision problem and Polynomial-time reduction

Primality test

A primality test is an algorithm for determining whether an input number is prime.

See Decision problem and Primality test

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.

See Decision problem and Prime number

Search problem

In the mathematics of computational complexity theory, computability theory, and decision theory, a search problem is a type of computational problem represented by a binary relation. Decision problem and search problem are computational problems.

See Decision problem and Search problem

String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

See Decision problem and String (computer science)

Theory (mathematical logic)

In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language.

See Decision problem and Theory (mathematical logic)

Time complexity

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.

See Decision problem and Time complexity

Travelling salesman problem

The travelling salesman problem, also known as the travelling salesperson 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 exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

See Decision problem and Travelling salesman problem

Turing degree

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. Decision problem and Turing degree are computability theory.

See Decision problem and Turing degree

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. Decision problem and undecidable problem are computability theory.

See Decision problem and Undecidable problem

Word problem (mathematics)

In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. Decision problem and word problem (mathematics) are computational problems.

See Decision problem and Word problem (mathematics)

Yes–no question

In linguistics, a yes–no question, also known as a binary question, a polar question, or a general question, is a question whose expected answer is one of two choices, one that provides an affirmative answer to the question versus one that provides a negative answer to the question.

See Decision problem and Yes–no question

See also

Computational problems

References

[1] https://en.wikipedia.org/wiki/Decision_problem

Also known as Decidability problems, Decidable problem, Decision problems, Decision procedure, Decision variant, Decision version, Solvable problem, Word problem (computability).