Computability & Complexity Theory

In these areas, the problems to be solved are the main concerns as well as their algorithms. We review the whole gamut of the problems, group them into classes according to their complexity, and look at the relationships between the classes. We want to know which problems are solvable and which are not; which problems are easy to solve and which are hard. We also want to understand why they are easy or hard. Both areas are based on a theoretical model of computation and a formal definition of important concepts such as problem, algorithm, problem complexity, algorithm efficiency, etc. The computational model used in these areas is the so-called Universal Turing Machine which was defined by Alan Turing in 1936. The problems that we concentrate on are so-called decision problems. Turing machines, complexity.

18 flashcards · Computer Science · by lakesare

What's an undecidable problem?
Decision problem that's proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. 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. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when ru…
What's Turing machine?
Turning machine consists of: a limitless memory for both data and algorithms, a moving head that can read from and write to each cell of the memory following the instructions in the algorithm. 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. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be construct…
What's non-deterministic Turing Machine?
NTM's next action is not completely determined by its state and the current symbol it sees (unlike a deterministic Turing machine). Deterministic Turing Machine In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation. A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left, right or neit…
How does nondeterministic Turing Machine know what action it should take given a certain state and input?
We can picture it as the luckiest possible guesser. How does the NTM "know" which of these actions it should take? There are two ways of looking at it.1. One is to say that the machine is the "luckiest possible guesser"; it always picks a transition that eventually leads to an accepting state, if there is such a transition.2. The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path"…
What's decision problem/Entscheidungsproblem?
A problem with: input: a statement output: true/false In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928.The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms.
Upper vs lower bound on the complexity of problems?
Upper bound - to prove an upper bound, we should just show a particular existing algorithm that solves a problem in T(n). Lower bound - the best algorithmic solution that is theoretically possible. The upper bound of a problem depends on the current state of algorithm development, while the lower bound is calculated and mathematically proved by theoreticians. To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running…
Open problem VS closed problem?
We can now divide problems into two broad classes, namely, open problems and close problems, according to the gap between the upper and lower bound of the problems. closed problem A problem is a closed problem if its upper and lower bounds are the same. open problem A problem is an open problem if its upper and lower bounds are different. For a closed problem, new algorithms may improve some factors within the Big-O but will not change the Big-O for the problem. For an open problem, we cannot b…
Tractable VS intractable problems?
A problem is said to be polynomially bounded if there is a worst case polynomial algorithm for it.Polynomial-time problems are those problems that are known and proved to be solvable in polynomial time. Intractable problems are those that are known and proved to be unsolvable in polynomial time. Note: 1. There are problems between the tractable and intractable, the two clearly defined classes, whose upper and lower bounds are inconsistent, for example, the problems with an exponential upper bou…
Deterministic VS nondeterministic Turing machine?
If a Turing machine has a nondeterministic transition function there can be multiple transitions from one state to many others when reading a character. Again this does not enhance the power of Turing machines. However nondeterministic Turing machines (as they are called then) may possibly decrease the computation time by a strong amount. This question is covered in the P versus NP-discussion and is not solved yet. Most scientists assume however that nondeterministic machines can work much fast…
How do these 3 complexity classes relate to each other? P NP NP-complete
P - Solvable in polynomial time NP - "YES" answers checkable in polynomial time NP-complete - The hardest or most expressive problems in NP
What does NP complexity class stand for?
Non-deterministic polynomial time N P is, informally speaking, the class of decision problems that can only be solved efficiently by the guess-and-verify technique: guess a solution, and verify that the proposed solution is indeed a solution. That is to say, loosely, for every problem in N P, a given proposed solution for a given input can be checked quickly, i.e. it can be checked in polynomial time if the solution satisfies all the requirements of the problem. Can be solved in polynomial time…
Name 2 Millennium prize problems.
Poincare conjecture - as of 2020, the Poincaré conjecture is the only solved Millennium problem. P vs NP
Name 2 definitions of the NP (nondeterministic polynomial time) complexity class.
'Yes' answer can be verified in polynomial time by a deterministic Turing machine. Can be solved in polynomial time by a non-deterministic Turing machine. Second definition is the basis for the abbreviation NP; "nondeterministic, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a non-deterministic way, while the second phase consists of…
What's P vs NP (P = NP?) problem?
P vs NP asks whether polynomial time algorithms exist for solving NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case. If P = NP, all NP problems will end up to be polynomial.
What 'problem A reduces to problem B' means?
We can use problem B to solve problem A. Solving B kills two birds with one stone.
How to prove a newly found problem Phd is NP-complete?
The common practice is to: Prove the new problem Phd is in NP. Prove a known NP-complete problem P can be transformed into Phd in polynomial time. This means that once we have identified a single NP-complete problem, f, in order to prove that another decision problem g is NP-complete, all we have to do is to find an efficient algorithm for transforming input instances for f into input instances for g. Other suggestions made in the poll included "Herculean", "formidable", Steiglitz's "hard-boile…
What was the first NP-complete problem?
SAT (Satisfiability) problem. In 1971 Steven Cook proved that SAT is NP-complete by showing that all problems in N P could be transformed to satisfiability. He used the fact that every problem in N P can be solved in polynomial time by a non-deterministic Turing machine. Most of the classical decision problems have now been determined as being in P or being NP-complete, but a number of important problems are still open. In particular, the problems called Primality and Composite number are both…
What's the definition of P complexity class?
All decision problems that can be solved by a deterministic Turing machine in a polynomial time.