Find link

Computational complexity not in Graph automorphism

language:

Find link is a tool written by Edward Betts.

Longer titles found: Computational complexity of mathematical operations (view), Computational complexity of matrix multiplication (view), Computational complexity theory (view), Electronic Colloquium on Computational Complexity (view), Asymptotic computational complexity (view), Computational Complexity Conference (view), Implicit computational complexity (view)

searching for Computational complexity 156 found (1608 total)

alternate case: computational complexity

Filter design (3,300 words) [view diff] exact match in snippet view article find links to article

filter required? Finite (in duration) impulse response required? Computational complexity Technology The required frequency response is an important parameter

Empirical risk minimization (1,618 words) [view diff] no match in snippet view article find links to article

In statistical learning theory, the principle of empirical risk minimization defines a family of learning algorithms based on evaluating performance over

Go and mathematics (1,727 words) [view diff] exact match in snippet view article find links to article

use in Go). Generalized Go is played on n × n boards, and the computational complexity of determining the winner in a given position of generalized Go

Polygon triangulation (1,386 words) [view diff] no match in snippet view article find links to article

In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) P into a set of triangles, i.e., finding a set of

Threshold theorem (1,061 words) [view diff] no match in snippet view article find links to article

In quantum computing, the threshold theorem (or quantum fault-tolerance theorem) states that a quantum computer with a physical error rate below a certain

Ray tracing (graphics) (7,806 words) [view diff] no match in snippet view article

In 3D computer graphics, ray tracing is a technique for modeling light transport for use in a wide variety of rendering algorithms for generating digital

Probabilistic analysis of algorithms (303 words) [view diff] exact match in snippet view article find links to article

probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption

Strong duality (265 words) [view diff] case mismatch in snippet view article find links to article

Retrieved October 3, 2011. Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv:1012.5568 [math.OC].

Knapsack problem (7,770 words) [view diff] no match in snippet view article find links to article

The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items

Rolling hash (2,011 words) [view diff] no match in snippet view article find links to article

A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input

Graph coloring (8,446 words) [view diff] exact match in snippet view article find links to article

S2CID 13131049 Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of

K-vertex-connected graph (772 words) [view diff] no match in snippet view article find links to article

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer

Monadic second-order logic (1,308 words) [view diff] exact match in snippet view article find links to article

equivalent to the inequality of NP and coNP, an open question in computational complexity. By contrast, when we wish to check whether a Boolean MSO formula

Unknotting problem (1,398 words) [view diff] exact match in snippet view article find links to article

in the complexity class P. First steps toward determining the computational complexity were undertaken in proving that the problem is in larger complexity

Full Rate (698 words) [view diff] exact match in snippet view article find links to article

of development (early 1990s) it was a good compromise between computational complexity and quality, requiring only on the order of a million additions

Least squares inference in phylogeny (698 words) [view diff] exact match in snippet view article find links to article

of phylogenetic trees. Science 155: 279-84. William H.E. Day, Computational complexity of inferring phylogenies from dissimilarity matrices, Bulletin

Cylindrical algebraic decomposition (430 words) [view diff] exact match in snippet view article find links to article

together with an algorithm for computing it. Collins' algorithm has a computational complexity that is double exponential in n. This is an upper bound, which

SBC (codec) (799 words) [view diff] exact match in snippet view article

obtain a reasonably good audio quality at medium bit rates with low computational complexity. As of A2DP version 1.3, the Low Complexity Subband Coding remains

Minesweeper (video game) (2,033 words) [view diff] no match in snippet view article

Minesweeper is a logic puzzle video game genre generally played on personal computers. The game features a grid of clickable tiles, with hidden "mines"

G.719 (522 words) [view diff] exact match in snippet view article find links to article

bit-allocation and low complexity lattice vector quantization. The computational complexity is quite low (18 floating-point MIPS) for an efficient high-quality

Mike Paterson (654 words) [view diff] exact match in snippet view article find links to article

publications, especially in the design and analysis of algorithms and computational complexity. Paterson's distinguished career was recognised with the EATCS

3-subset meet-in-the-middle attack (1,556 words) [view diff] exact match in snippet view article find links to article

another, thus allowing for a basic MITM attack that reduces the computational complexity from 2 112 ( = 2 2 × 56 ) {\displaystyle 2^{112}(=2^{2\times 56})}

Antichain (1,090 words) [view diff] no match in snippet view article find links to article

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are

Biclique attack (3,173 words) [view diff] exact match in snippet view article find links to article

2019[update]) the best publicly known single-key attack on AES. The computational complexity of the attack is 2 126.1 {\displaystyle 2^{126.1}} , 2 189.7 {\displaystyle

Instance-based learning (292 words) [view diff] exact match in snippet view article find links to article

worst case, a hypothesis is a list of n training items and the computational complexity of classifying a single new instance is O(n). One advantage that

Neil Immerman (332 words) [view diff] exact match in snippet view article find links to article

currently applying to research in model checking, database theory, and computational complexity theory. Professor Immerman is an editor of the SIAM Journal on

Disjunctive normal form (2,152 words) [view diff] exact match in snippet view article find links to article

conflicting literals. An important variation used in the study of computational complexity is k-DNF. A formula is in k-DNF if it is in DNF and each conjunction

Parity function (1,050 words) [view diff] exact match in snippet view article find links to article

number of 2 n − 1 clauses of length n. Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya showing the size of a Boolean

Neil Immerman (332 words) [view diff] exact match in snippet view article find links to article

currently applying to research in model checking, database theory, and computational complexity theory. Professor Immerman is an editor of the SIAM Journal on

CA-duality (360 words) [view diff] exact match in snippet view article find links to article

asymptotically anti-de Sitter background corresponds to quantum computational complexity, and that black holes produce complexity at the fastest possible

Evolutionary algorithm (4,553 words) [view diff] exact match in snippet view article find links to article

most real applications of EAs, computational complexity is a prohibiting factor. In fact, this computational complexity is due to fitness function evaluation

Martin Demaine (695 words) [view diff] exact match in snippet view article find links to article

unfolding objects out of flat materials such as paper and on the computational complexity of games and puzzles. Martin and Erik were fans of Martin Gardner

Levenshtein distance (2,434 words) [view diff] no match in snippet view article find links to article

In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences

Triangular network coding (454 words) [view diff] exact match in snippet view article find links to article

and decoding computational complexity. While linear encoding and decoding over GF(2) alleviates the concern of high computational complexity, coding over

Open-shop scheduling (624 words) [view diff] no match in snippet view article find links to article

Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of

Vincent Blondel (715 words) [view diff] exact match in snippet view article find links to article

computer science. He is mostly known for his contributions in computational complexity in control, multi-agent coordination and complex networks. Blondel

Self-complementary graph (366 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary

TwixT (1,588 words) [view diff] no match in snippet view article find links to article

TwixT is a two-player strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games

Chris Umans (594 words) [view diff] exact match in snippet view article find links to article

California Institute of Technology. He is known for work on algorithms, computational complexity, algebraic complexity, and hardness of approximation. Umans studied

Rush Hour (puzzle) (841 words) [view diff] no match in snippet view article

Rush Hour is a sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. It is now being manufactured

List of lemmas (525 words) [view diff] no match in snippet view article find links to article

This following is a list of lemmas (or, "lemmata", i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list

Sieve of Atkin (1,994 words) [view diff] no match in snippet view article find links to article

In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes

Dissipative particle dynamics (1,682 words) [view diff] exact match in snippet view article find links to article

equilibrium state. A series of new DPD algorithms with reduced computational complexity and better control of transport properties are presented. The algorithms

Diffie–Hellman problem (946 words) [view diff] no match in snippet view article find links to article

The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography and serves

Extremal optimization (1,490 words) [view diff] exact match in snippet view article find links to article

self-organised critical process. Another piece in the puzzle is work on computational complexity, specifically that critical points have been shown to exist in

Kempner function (846 words) [view diff] no match in snippet view article find links to article

In number theory, the Kempner function S ( n ) {\displaystyle S(n)} is defined for a given positive integer n {\displaystyle n} to be the smallest number

Sanjeev Arora (433 words) [view diff] case mismatch in snippet view article find links to article

Mathematicians. He is a coauthor (with Boaz Barak) of the book Computational Complexity: A Modern Approach. He was a founder of Princeton's Center for

Phutball (717 words) [view diff] no match in snippet view article find links to article

Phutball (short for Philosopher's Football) is a two-player abstract strategy board game described in Elwyn Berlekamp, John Horton Conway, and Richard

Modular arithmetic (3,646 words) [view diff] no match in snippet view article find links to article

In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers

Computational indistinguishability (420 words) [view diff] exact match in snippet view article find links to article

In computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the

Uniformity (157 words) [view diff] exact match in snippet view article find links to article

composition or character Uniformity (complexity), a concept in computational complexity theory Uniformity (philosophy), the concept that the same natural

Order dimension (1,205 words) [view diff] no match in snippet view article find links to article

In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial

G.722.1 (796 words) [view diff] exact match in snippet view article find links to article

using a Modulated Lapped Transform (MLT), a type of MDCT. The computational complexity is quite low (5.5 floating-point MIPS) for an efficient high-quality

Bipartite matroid (363 words) [view diff] no match in snippet view article find links to article

In mathematics, a bipartite matroid is a matroid all of whose circuits have even size. A uniform matroid U n r {\displaystyle U{}_{n}^{r}} is bipartite

Graph embedding (1,744 words) [view diff] no match in snippet view article find links to article

In topological graph theory, an embedding (also spelled imbedding) of a graph G {\displaystyle G} on a surface Σ {\displaystyle \Sigma } is a representation

Core (graph theory) (399 words) [view diff] no match in snippet view article

In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms. Graph C {\displaystyle

English draughts (2,521 words) [view diff] no match in snippet view article find links to article

Draughts (British English) or checkers (American English), also called straight checkers or simply draughts, is a form of the strategy board game checkers

Method of fundamental solutions (1,175 words) [view diff] exact match in snippet view article find links to article

of a boundary discretization numerical technique and reduce the computational complexity by one dimensionality and have particular edge over the domain-type

Quadratic assignment problem (773 words) [view diff] no match in snippet view article find links to article

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research

Tile-matching video game (2,747 words) [view diff] no match in snippet view article find links to article

A tile-matching video game is a type of puzzle video game where the player manipulates tiles in order to make them disappear according to a matching criterion

Caterpillar tree (1,205 words) [view diff] no match in snippet view article find links to article

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path. Caterpillars were first

Hamming graph (651 words) [view diff] no match in snippet view article find links to article

Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science

Quadratic bottleneck assignment problem (224 words) [view diff] no match in snippet view article find links to article

In mathematics, the quadratic bottleneck assignment problem (QBAP) is one of the fundamental combinatorial optimization problems in the branch of optimization

Matching polynomial (882 words) [view diff] no match in snippet view article find links to article

In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of

Master theorem (analysis of algorithms) (1,978 words) [view diff] no match in snippet view article

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis for many recurrence relations that

Unit disk graph (1,379 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one

Path cover (446 words) [view diff] no match in snippet view article find links to article

Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path

Ghost (game) (1,086 words) [view diff] no match in snippet view article

Ghost (also known as ghosts or pig) is a written or spoken word game in which players take turns to extend the letters of a word without completing a valid

Christofides algorithm (1,404 words) [view diff] no match in snippet view article find links to article

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on

Fractional graph isomorphism (415 words) [view diff] no match in snippet view article find links to article

In graph theory, a fractional isomorphism of graphs whose adjacency matrices are denoted A and B is a doubly stochastic matrix D such that DA = BD. If

Unit disk graph (1,379 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one

Matching (graph theory) (2,938 words) [view diff] no match in snippet view article

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In

Circuit (616 words) [view diff] exact match in snippet view article find links to article

circuit, a mathematical object of computational complexity Circuit complexity, a branch of computational complexity theory Cycle (graph theory), a closed

Shakashaka (199 words) [view diff] exact match in snippet view article find links to article

Erik D.; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), "Computational complexity and an integer programming model of Shakashaka", IEICE Transactions

Graph power (1,260 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two

Director string (675 words) [view diff] exact match in snippet view article find links to article

and Mackie as a mechanism for understanding and controlling the computational complexity cost of beta reduction. In beta reduction, one defines the value

Shikaku (251 words) [view diff] no match in snippet view article find links to article

Shikaku (四角に切れ, Shikaku ni Kire, also anglicised as Divide by Box or Rectangles) is a logic puzzle published by Nikoli. The game was invented by Yoshiano

Series-parallel partial order (2,253 words) [view diff] no match in snippet view article find links to article

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two

Convex hull algorithms (2,326 words) [view diff] exact match in snippet view article find links to article

For a finite set of points in the plane, the lower bound on the computational complexity of finding the convex hull represented as a convex polygon is easily

Graph sandwich problem (538 words) [view diff] no match in snippet view article find links to article

In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched"

Derangement (2,212 words) [view diff] no match in snippet view article find links to article

In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words

Kayles (907 words) [view diff] no match in snippet view article find links to article

Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns

Tanner graph (371 words) [view diff] no match in snippet view article find links to article

In coding theory, a Tanner graph is a bipartite graph that can be used to express constraints (typically equations) that specify an error correcting code

List of Jewish American computer scientists (1,638 words) [view diff] exact match in snippet view article find links to article

(Turing Award (1995)), Venezuelan-American computer scientist; computational complexity, parents of Avrim Blum (Co-training) Dan Bricklin, creator of the

Information Processing Letters (520 words) [view diff] exact match in snippet view article find links to article

science, including algorithms, formal languages and automata, computational complexity, computational logic, distributed and parallel algorithms, computational

Borwein's algorithm (1,545 words) [view diff] case mismatch in snippet view article find links to article

the book Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity. These two are examples of a Ramanujan–Sato series. The related

Grötzsch's theorem (1,189 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors

Grötzsch's theorem (1,189 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors

Holy Grail (disambiguation) (273 words) [view diff] exact match in snippet view article

as could a theory of everything for physics, or P vs. NP for computational complexity theory) Holy Grail may also refer to: "Holy Grail" (Hunters & Collectors

Numberlink (533 words) [view diff] no match in snippet view article find links to article

Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid. The player has to pair up all the matching numbers on the grid

Structured program theorem (2,782 words) [view diff] no match in snippet view article find links to article

The structured program theorem, also called the Böhm–Jacopini theorem, is a result in programming language theory. It states that a class of control-flow

Discrete logarithm (2,506 words) [view diff] exact match in snippet view article find links to article

method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem, along with its application,

K-minimum spanning tree (1,057 words) [view diff] exact match in snippet view article find links to article

graphs with only two distinct edge weights. Because of the high computational complexity of finding an optimal solution to the k-minimum spanning tree,

Graph toughness (636 words) [view diff] no match in snippet view article find links to article

In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer

Clique-width (2,057 words) [view diff] exact match in snippet view article find links to article

polynomial increases with the clique-width, and evidence from computational complexity theory shows that this dependence is likely to be necessary. The

Exact coloring (534 words) [view diff] no match in snippet view article find links to article

In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. That is

Edge dominating set (673 words) [view diff] no match in snippet view article find links to article

In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An

Nurikabe (puzzle) (1,277 words) [view diff] no match in snippet view article

Nurikabe (hiragana: ぬりかべ) is a binary determination puzzle named for Nurikabe, an invisible wall in Japanese folklore that blocks roads and delays foot

Pancyclic graph (1,614 words) [view diff] no match in snippet view article find links to article

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from

Kovner–Besicovitch measure (467 words) [view diff] no match in snippet view article find links to article

In plane geometry the Kovner–Besicovitch measure is a number defined for any bounded convex set describing how close to being centrally symmetric it is

Criss-cross algorithm (2,432 words) [view diff] no match in snippet view article find links to article

In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm

Ordo (266 words) [view diff] exact match in snippet view article find links to article

and ending in a rest Big O notation in calculation of algorithm computational complexity Orda (organization), also ordo or horde, was a nomadic palace for

Matchstick graph (1,597 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line

Theory of Computing Systems (101 words) [view diff] exact match in snippet view article find links to article

research from all areas of theoretical computer science, such as computational complexity, algorithms and data structures, or parallel and distributed algorithms

Domatic number (973 words) [view diff] no match in snippet view article find links to article

In graph theory, a domatic partition of a graph G = ( V , E ) {\displaystyle G=(V,E)} is a partition of V {\displaystyle V} into disjoint sets V 1 {\displaystyle

Shannon switching game (1,327 words) [view diff] no match in snippet view article find links to article

The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father

Alternating tree automata (98 words) [view diff] no match in snippet view article find links to article

In automata theory, an alternating tree automaton (ATA) is an extension of nondeterministic tree automaton as same as alternating finite automaton extends

Induced matching (809 words) [view diff] no match in snippet view article find links to article

In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a matching)

NP (285 words) [view diff] exact match in snippet view article find links to article

Polynomial, a computational complexity class NP-complete, a class of decision problems NP-hard, a class of problems in computational complexity Co-NP, a complexity

Eulerian matroid (1,078 words) [view diff] no match in snippet view article find links to article

In matroid theory, an Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits. In a uniform matroid U n

Markov decision process (5,156 words) [view diff] exact match in snippet view article find links to article

for finite MDPs. Thus, decision problems based on MDPs are in computational complexity class P. However, due to the curse of dimensionality, the size

Light Up (puzzle) (914 words) [view diff] no match in snippet view article

Light Up (Japanese: 美術館 bijutsukan, art gallery), also called Akari (明かり, light) is a binary-determination logic puzzle published by Nikoli. As of 2011

Havannah (board game) (989 words) [view diff] no match in snippet view article

Havannah is a two-player abstract strategy board game invented by Christian Freeling. It belongs to the family of games commonly called connection games;

Computers and Intractability (779 words) [view diff] exact match in snippet view article find links to article

as well. [...] Garey and Johnson has the best introduction to computational complexity I have ever seen." List of NP-complete problems Garey, M. R.; Johnson

Induced matching (809 words) [view diff] no match in snippet view article find links to article

In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a matching)

Eulerian matroid (1,078 words) [view diff] no match in snippet view article find links to article

In matroid theory, an Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits. In a uniform matroid U n

Alternating tree automata (98 words) [view diff] no match in snippet view article find links to article

In automata theory, an alternating tree automaton (ATA) is an extension of nondeterministic tree automaton as same as alternating finite automaton extends

Exponentiation by squaring (3,380 words) [view diff] no match in snippet view article find links to article

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number

W1 (236 words) [view diff] exact match in snippet view article find links to article

weathering Wrestle-1, a Japanese professional wrestling promotion The computational complexity class W[1] in parameterized complexity The Apple W1 wireless pairing

Art gallery problem (2,530 words) [view diff] exact match in snippet view article find links to article

hdl:2043/11487, MR 3044626, S2CID 1458082. Lee, D. T.; Lin, A. K. (1986), "Computational complexity of art gallery problems", IEEE Transactions on Information Theory

Game of the Amazons (983 words) [view diff] no match in snippet view article find links to article

The Game of the Amazons (in Spanish, El Juego de las Amazonas; often called Amazons for short) is a two-player abstract strategy game invented in 1988

Continuous knapsack problem (518 words) [view diff] exact match in snippet view article find links to article

in the formulation of a problem can have a large impact on its computational complexity. An instance of either the continuous or classic knapsack problems

Bag (puzzle) (342 words) [view diff] no match in snippet view article

Bag (also called Corral or Cave) is a binary-determination logic puzzle published by Nikoli. Bag is played on a rectangular grid, usually of dashed lines

Semantic security (1,434 words) [view diff] exact match in snippet view article find links to article

the message length (and not the ciphertext). This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy

Checkers (3,257 words) [view diff] no match in snippet view article find links to article

Checkers (American English), also known as draughts (/drɑːfts, dræfts/; British English), is a group of strategy board games for two players which involve

Ptolemaic graph (808 words) [view diff] no match in snippet view article find links to article

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek

Time-inhomogeneous hidden Bernoulli model (240 words) [view diff] exact match in snippet view article find links to article

programming at state-level in TI-HBM decoding process. Thus, the computational complexity of TI-HBM for probability evaluation and state estimation is O

Perfectly orderable graph (1,149 words) [view diff] no match in snippet view article find links to article

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering

Thickness (graph theory) (1,268 words) [view diff] no match in snippet view article

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists

RAC drawing (1,190 words) [view diff] no match in snippet view article find links to article

In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments

Tatamibari (166 words) [view diff] no match in snippet view article find links to article

Tatamibari (Japanese: タタミバリ) is a type of logic puzzle designed and published by Nikoli. The puzzle is based on Japanese tatami mats. A Tatamibari puzzle

Yuri Gurevich (836 words) [view diff] exact match in snippet view article find links to article

University of Michigan, where he started to work on various aspects of computational complexity theory including average case complexity. He became one of the

Kinodynamic planning (305 words) [view diff] exact match in snippet view article find links to article

the original PTAS algorithms (i.e., none have a provably lower computational complexity). Donald, B.; Xavier, P.; Canny, J.; Reif, J. (1993), "Kinodynamic

PTAS (71 words) [view diff] exact match in snippet view article find links to article

currency PTAS reduction, an approximation-preserving reduction in computational complexity theory Preferential trading area, another term for a trade bloc

Tentai Show (635 words) [view diff] no match in snippet view article find links to article

Tentai Show (Japanese: 天体ショー tentai shō), also known by the names Tentaisho, Galaxies, Spiral Galaxies, or Sym-a-Pix, is a binary-determination logic puzzle

Kinodynamic planning (305 words) [view diff] exact match in snippet view article find links to article

the original PTAS algorithms (i.e., none have a provably lower computational complexity). Donald, B.; Xavier, P.; Canny, J.; Reif, J. (1993), "Kinodynamic

Distinguishing coloring (1,309 words) [view diff] exact match in snippet view article find links to article

Alexander; Sundaram, Ravi (1998), "A note on the asymptotics and computational complexity of graph distinguishability", Electronic Journal of Combinatorics

AC0 (769 words) [view diff] exact match in snippet view article find links to article

{\mathsf {AC}}_{2}^{0}} .: 148 Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. pp. 117–118, 287

Angular resolution (graph drawing) (1,665 words) [view diff] exact match in snippet view article

ISBN 978-3-540-58434-6. Garg, Ashim; Tamassia, Roberto (1995), "On the computational complexity of upward and rectilinear planarity testing", in Tamassia, Roberto;

Lowness (94 words) [view diff] exact match in snippet view article find links to article

Low (complexity), a relationship between complexity classes in computational complexity theory Prince Lowness, a character in the Terrific Whatzit DC Comics

PTAS (71 words) [view diff] exact match in snippet view article find links to article

currency PTAS reduction, an approximation-preserving reduction in computational complexity theory Preferential trading area, another term for a trade bloc

Random neural network (1,063 words) [view diff] exact match in snippet view article find links to article

includes feedback loops (it is also a recurrent neural network) is of computational complexity O(n^3) (the number of computations is proportional to the cube

De Casteljau's algorithm (2,000 words) [view diff] exact match in snippet view article find links to article

stable when compared to direct evaluation of polynomials. The computational complexity of this algorithm is O ( d n 2 ) {\displaystyle O(dn^{2})} , where

Christopher Cherniak (1,597 words) [view diff] exact match in snippet view article find links to article

idealizations. This is part of the philosophical significance of computational complexity. This research program proceeds from a holistic rather than compartmentalized

Linear arboricity (863 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned

Godfried Toussaint (1,217 words) [view diff] exact match in snippet view article find links to article

the convex hull of a planar point set. This algorithm exhibits a computational complexity with expected value linear in the size of the input. In 1980 he

Walter Savitch (195 words) [view diff] exact match in snippet view article find links to article

language processing and mathematical linguistics. He was focused on computational complexity as it applies to genetics and biology for over 10 years. Aside

Tutte polynomial (5,377 words) [view diff] exact match in snippet view article find links to article

{\displaystyle (x,y)} , one can define a rational analogue of #P. The computational complexity of exactly computing T G ( x , y ) {\displaystyle T_{G}(x,y)} falls

Matroid girth (779 words) [view diff] no match in snippet view article find links to article

In matroid theory, a mathematical discipline, the girth of a matroid is the size of its smallest circuit or dependent set. The cogirth of a matroid is

Halin graph (2,157 words) [view diff] no match in snippet view article find links to article

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four

Segmentation-based object categorization (1,901 words) [view diff] no match in snippet view article find links to article

The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily

Victor Shoup (297 words) [view diff] exact match in snippet view article find links to article

online. He has proved (while at IBM Zurich) a lower bound to the computational complexity for solving the discrete logarithm problem in the generic group

Blum (160 words) [view diff] exact match in snippet view article find links to article

Washington Blum axioms, in computational complexity theory Blum integer, in mathematics Blum's speedup theorem, in computational complexity theory Blum (surname)

Japaridze's polymodal logic (1,202 words) [view diff] no match in snippet view article find links to article

Japaridze's polymodal logic (GLP) is a system of provability logic with infinitely many provability modalities. This system has played an important role

SL (434 words) [view diff] exact match in snippet view article find links to article

top-level domain for Sierra Leone SL (complexity), a class of computational complexity Scientific Linux, a Linux distribution Service Loading, a variant

MaxDDBS (222 words) [view diff] exact match in snippet view article find links to article

Degree-Diameter Problem has been active since the 1960s. Regarding its computational complexity, the problem is NP-hard, and not in APX (i.e. it cannot be approximated