A cycle of edges passing through every vertex exactly once

No.

and every other hotel lol

If the points are ordered counterclockwise, then the triangle is facing the camera. This incidentally aligns with historical conventions like the right-hand rule and Euler angles.

It stores all the *unique* vertices of the triangles you're drawing. You'd then use an index buffer to identify specific vertices in the vertex buffer with specific vertices in your triangles.

Gamma encoding of images is used to optimize the usage of bits when encoding an image, or bandwidth used to transport an image, by taking advantage of the non-linear manner in which humans perceive light and color. The human perception of brightness (lightness), under common illumination conditions (neither pitch black nor blindingly bright), follows an approximate power function (which has no relation to the gamma function), with greater sensitivity to relative differences between darker tones than between lighter tones.

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.

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.

Types checked and enforced at runtime

Mipmaps (also MIP maps) or pyramids are pre-calculated, optimized sequences of images, each of which is a progressively lower resolution representation of the previous. The height and width of each image, or level, in the mipmap is a factor of two smaller than the previous level. They are intended to increase rendering speed and reduce aliasing artifacts. The letters MIP in the name are an acronym of the Latin phrase multum in parvo, meaning "much in little".

Probably not

It is used in conjuction with a vertex buffer --- the set of unique vertices in your triangles --- to associate specific vertices in your vertex buffer to specific vertices in your triangles.

A variable's type cannot change over its lifetime. Nuanced though because most languages support aliasing which can make it appear as if a variable changed type, even though it hasn't; syntactic sugar merely drops the old variable and creates a new one with the same name

A BindGroup describes a set of resources and how they can be accessed by a shader. TODO: maybe this is a WGSL thing, not a wgpu thing.

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.

Copy Trait: - Bitwise copy, automatic and implicit. - No heap-allocated fields. - Requires all fields to be Copy. Clone Trait: - Custom logic for duplication, call .clone() explicitly. - Can impl Clone even if there are heap-allocated fields.

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

is NP-complete

date +%s

Is in P

100 million

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

A variable's type can change and, typically, implicit conversions are commonplace

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

Nondeterministic Polynomial Time

Types checked and enforced at compile time

Normal mapping is a texture mapping technique used for faking the lighting of bumps and dents – an implementation of bump mapping. It is used to add details without using more polygons. A common use of this technique is to greatly enhance the appearance and details of a low polygon model by generating a normal map from a high polygon model or height map.

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.

width : height

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.

A uniform is a global Shader variable. These act as parameters that the user of a shader program can pass to that program. Uniforms are so named because they do not change from one shader invocation to the next within a particular rendering call thus their value is uniform among all invocations. This makes them unlike shader stage inputs and outputs, which are often different for each invocation of a shader stage.

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