A cycle of edges passing through every vertex exactly once

and every other hotel lol

P :: R — The Recursive or decidable problems. NP :: RE — The Recursively Enumerable or problems whose solutions can be verified in finite time. We know R != RE.

Given a set of linear inequalities in many variables, determine whether they are mutually consistent, namely, whether there are real values for the variables satisfying all inequalities. Has many applications. Is in P. It's also in NP intersect coNP: the NP witness is a valid point. The coNP witness is a linear combination of the inequalities producing a contradiction, e.g., 0 > 1.

- The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. - This problem is a special case of the subgraph isomorphism problem,which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. - Since the graph isomorphism problem is neither known to be NP-complete nor known to be tractable, researchers have sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem.

yes

Is in NP. Not known to be NP-complete, P, or co-NP-complete. In BQP due to Shor's algorithm.

(also known as Russell's antinomy) is a set-theoretic paradox published by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains an unrestricted comprehension principle leads to contradictions. The paradox had already been discovered independently in 1899 by the German mathematician Ernst Zermelo. However, Zermelo did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other academics at the University of Göttingen. At the end of the 1890s, Georg Cantor – considered the founder of modern set theory – had already realized that his theory would lead to a contradiction, as he told Hilbert and Richard Dedekind by letter. Let R = { x | x not in x }. Then R in R implies R not in R.

In the late 1960s by Cobham, Edmonds, and Rabin

A theory T is syntactically complete if for every sentence of the language 𝜑 it is true that 𝑇 ⊢ 𝜑 or 𝑇 ⊢ ¬𝜑 . Decidability implies completeness. Incompleteness implies undecidability. But decidable != complete; a complete language could be undecidable.

The 1960s

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. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced using logical rules and axioms. The problem was posed in 1928 by David Hilbert and Wilhelm Ackermann. It was answered in the negative by Alonzo Church and Alan Turing in independent papers in 1936.

Probably not

Finds the maximum (potentially perfect) matching of a graph in polynomial time.

Church proved that there is no computable function which decides, for two given λ-calculus expressions, whether they are equivalent or not. He relied heavily on earlier work by Stephen Kleene.

A theory T is decidable if there exists an effective procedure to determine whether 𝑇 ⊢ 𝜑 where 𝜑 is any sentence of the language. Decidability implies completeness. Incompleteness implies undecidability. But decidable != complete; a complete language could be undecidable.

Complement of polynomial time algorithms. It's equal to P.

is NP-complete

Was recast in 1928 at the Bologna International Congress as three questions: "He posed three questions: i.e. #1: Was mathematics complete? #2: Was mathematics consistent? #3: Was mathematics decidable?"

Is in P

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

First algorithm to show that primality testing is in P. Of extreme theoretical importance, but never used in practice.

Is NP-complete

Known for 21 NP-complete problems published in a paper in 1972, among many other things.

Nondeterministic Polynomial Time

The nondeterminism captures the ability of a hypothetical nondeterministic machine to "guess" a witness (if one exists) and then verify it deterministically.

Is NP-complete in existing models

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. Turing reduced the question of the existence of an 'algorithm' or 'general method' able to solve the Entscheidungsproblem to the question of the existence of a 'general method' which decides whether any given Turing machine halts or not (the halting problem). If 'algorithm' is understood as meaning a method that can be represented as a Turing machine, and with the answer to the latter question negative (in general), the question about the existence of an algorithm for the Entscheidungsproblem also must be negative (in general).

Which knots on 3-dimensional manifolds bound a surface of genus <= g? Is NP-complete. This is a little confusing because a very similar problem, the uknotting problem, the specific case where g = 0, is not known to be NP-hard — there might be a polynomial time solution — and is in NP intersect coNP.

A problem (not necessarily in the complexity class C) is C-hard if every problem in C can be reduced to it in polynomial time.

Yes

Given a list of permutations on n elements, can the first one be generated by the rest? Is in P

is NP-complete in existing models

A graph that can be embedded in the plane without any edges crossing. Linear-time algorithms were discovered by Hopcroft and Tarjan in 1974.

Basically linear programming but with only integer solutions. Is NP complete

States that SAT is NP-complete

Stephen Cook in 1971 and Leonid Levin in 1973

C is in coNP if it's easy to certify that an object does NOT have property C. Additionally, a set C is in coNP if and only if its complement is in NP.

is NP-complete