Find link

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 151 found (1611 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].

Graph coloring (8,459 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

Knapsack problem (7,799 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

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

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

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

Triangulation (computer vision) (2,384 words) [view diff] no match in snippet view article

In computer vision, triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to

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

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

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

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the

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"

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})}

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

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

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

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

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

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

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

Disjunctive normal form (2,191 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

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

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

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

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

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

Extremal optimization (1,489 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

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

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

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

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

Rush Hour (puzzle) (837 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

Dissipative particle dynamics (1,678 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

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

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

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

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

Modular arithmetic (3,644 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

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

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

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

English draughts (2,520 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Integral polytope (947 words) [view diff] no match in snippet view article find links to article

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it

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

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

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"

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

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

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

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

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

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

Series-parallel partial order (2,259 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

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

Alternating finite automaton (808 words) [view diff] exact match in snippet view article find links to article

Holzer, Markus; Kutrib, Martin (2011-03-01). "Descriptional and computational complexity of finite automata—A survey". Information and Computation. 209

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

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

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

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

Quotient graph (598 words) [view diff] exact match in snippet view article find links to article

isomorphism. Given an n-vertex cubic graph G and a parameter k, the computational complexity of determining whether G can be obtained as a quotient of a planar

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,

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

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

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,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

approximations of a given filter shape up to a desired error or computational complexity. Freeman, W. T. & Adelson, E. H. (1991). "The design and use of

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

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

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

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;

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

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

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

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

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

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

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

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

Checkers (3,267 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

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

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

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

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

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

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

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;

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named after

Maximum cut (3,125 words) [view diff] no match in snippet view article find links to article

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary