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 157 found (1833 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 parameterEmpirical 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 overGo 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 GoPolygon 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 ofProbabilistic 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 assumptionThreshold 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 certainRay tracing (graphics) (7,799 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 digitalStrong 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,460 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 ofRolling hash (2,015 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 inputKnapsack problem (7,744 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 itemsMonadic 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 formulaK-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 fewerUnknotting 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 complexityTriangulation (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 toFull 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 additionsLeast 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, BulletinCylindrical 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, whichSBC (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 remainsGraph 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 theMike 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 EATCS3-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})}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-qualityMinesweeper (video game) (2,037 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"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 areNeil 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 onBiclique 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 {\displaystyleInstance-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 thatDisjunctive 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 conjunctionParity 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 BooleanCA-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 possibleMartin 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 GardnerEvolutionary algorithm (4,543 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 evaluationTriangular 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 overOpen-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 ofVincent 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. BlondelChris 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 studiedLevenshtein distance (2,487 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 sequencesExtremal 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 inSelf-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-complementaryTwixT (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 gamesRush Hour (puzzle) (836 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 manufacturedList 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 listSieve 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 EratosthenesDiffie–Hellman problem (954 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 servesDissipative 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 algorithmsKempner 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 numberPhutball (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 RichardSanjeev 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 forComputational 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 theG.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-qualityOrder 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 partialCore (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 {\displaystyleBipartite 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 bipartiteGraph 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 representationQuadratic bottleneck assignment problem (232 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 optimizationMethod 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-typeCaterpillar 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 firstHamming 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 scienceEnglish draughts (2,518 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 checkersQuadratic 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 researchGhost (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 validMatching 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 ofShakashaka (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 TransactionsUnit 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 oneClosest pair of points problem (1,215 words) [view diff] exact match in snippet view article find links to article
that were treated at the origins of the systematic study of the computational complexity of geometric algorithms. Randomized algorithms that solve the problemChristofides 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, onTile-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 criterionGraph 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 twoCircuit (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 closedIntegral 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, itGraph 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"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 pathMatching (graph theory) (3,032 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. InFractional 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. IfTanner graph (375 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 codeSeries-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 twoMaster 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 thatConvex 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 easilyKayles (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 turnsBorwein'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 relatedDirector string (677 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 valueModular 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 numbersList 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 theInformation 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, computationalNumberlink (615 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 gridShikaku (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 YoshianoExact coloring (520 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 isAlternating 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. 209Grö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 colorsEdge 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. AnStructured program theorem (2,912 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-flowQuotient graph (621 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 planarHoly 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 & CollectorsK-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 integerPancyclic 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 fromClique-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. TheShannon 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 "fatherMatchstick 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 lineKovner–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 isCriss-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 algorithmTheory 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 algorithmsNurikabe (puzzle) (1,284 words) [view diff] no match in snippet view article
Nurikabe (hiragana: ぬりかべcode: jpn promoted to code: ja ) is a binary determination puzzle named for Nurikabe, an invisible wall in Japanese folklore thatOrdo (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 forDomatic 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 {\displaystyleAlternating 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 extendsInduced 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 complexityArt 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 TheoryHavannah (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;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 2011Induced 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)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 pairingEulerian 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 nExponentiation by squaring (3,382 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 numberComputers 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.; JohnsonGame of the Amazons (986 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 1988Perfectly 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 orderingBag (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 linesPtolemaic 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 GreekMarkov decision process (5,169 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 sizeSemantic security (1,435 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 secrecyContinuous 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 problemsThickness (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 existsTime-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 OTentai 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 puzzleDiscrete logarithm (2,537 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,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 blocYuri 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 theKinodynamic 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), "KinodynamicLowness (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 ComicsTatamibari (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 puzzleCheckers (3,420 words) [view diff] no match in snippet view article find links to article
Checkers (American English), known as draughts outside of the United States (/drɑːfts, dræfts/; Commonwealth English), is a group of strategy board gamesRAC 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 segmentsEquitable coloring (2,290 words) [view diff] exact match in snippet view article find links to article
Eldridge, S. E. (1978), "Packings of graphs and applications to computational complexity", Journal of Combinatorial Theory, Series B, 25 (2): 105–124, doi:10AC0 (778 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, 287Distinguishing 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 CombinatoricsLinear 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 partitionedDe 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})} , whereAngular 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;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 compartmentalizedRandom 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 cubeVictor 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 groupJoan Feigenbaum (605 words) [view diff] exact match in snippet view article find links to article
of her career, including cryptography, security, and privacy; computational complexity; algorithmic mechanism design; massive-data-stream algorithmics;String graph (1,532 words) [view diff] no match in snippet view article find links to article
In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graphGodfried 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 heWalter 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. AsideHalin graph (2,300 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 fourTutte 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)} fallsSegmentation-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 primarilySuccinct game (1,887 words) [view diff] case mismatch in snippet view article find links to article
Zero-Sum Games". Proceedings of the 20th Annual IEEE Conference on Computational Complexity. IEEE Computer Society. pp. 323–332. ISBN 0-7695-2364-1. RetrievedMatroid 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 isBlum (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)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 afterBramble (graph theory) (955 words) [view diff] no match in snippet view article
In graph theory, a bramble for an undirected graph G is a family of connected subgraphs of G that all touch each other: for every pair of disjoint subgraphsSL (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