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

extremal method and pigeon hole principle. let n be maximum number of edges on a face. every adjacent face must have between 3 and n edges. but there are n adjacent faces. by pigeonhole, some two must have the same number of edges.

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

Nondeterministic Polynomial Time

Two matrices, M: m-by-n, M': n-by-p. Let r < n. Let A = M[:, :r], A' = M'[:r, :], B = [:, r:], B' = [r:, :]. Then the product MM' = AA' + BB'. You can partitions two matrices by r rows and columns, respectively and sum their respective products. The rote method of matrix multiplication is the special case r = 1. You can generalize this further to arbitrary tilings and conduct matrix multiplication of the partitions (sub-matrices) in the same way you would conduct normal matrix multiplication.

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

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.

describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. proved independently by Jacques Hadamard and Charles Poussin in 1896. Used ideas from Riemann. pi(n) ~ n/log(n)

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.

The set of all invertible n-by-n matrices

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment (possibly empty). For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

Yes

An affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments.

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

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

For a > b, GCD(a, b) = GCD(b, r = a%b). You can use the Division Theorem to prove the equation holds.

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