Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: List of complexity classes (view)

searching for Complexity class 109 found (305 total)

Parameterized complexity (2,682 words) [view diff] exact match in snippet view article find links to article

f is an arbitrary function depending only on k. The corresponding complexity class is called FPT. For example, there is an algorithm that solves the vertex

Counting problem (complexity) (169 words) [view diff] exact match in snippet view article

Boaz (Spring 2006). "Complexity of counting" (PDF). Princeton University. "counting problem". PlanetMath. "counting complexity class". PlanetMath. v t e

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

polynomial time algorithm; that is, whether the problem lies in the complexity class P. First steps toward determining the computational complexity were

Alexei Kitaev (509 words) [view diff] exact match in snippet view article find links to article

Institute for Theoretical Physics. He is also known for introducing the complexity class QMA and showing the 2-local Hamiltonian problem is QMA-complete, the

Stephen Cook (1,510 words) [view diff] exact match in snippet view article find links to article

He named the complexity class NC after Nick Pippenger. The complexity class SC is named after him. The definition of the complexity class AC0 and its hierarchy

Random oracle (1,775 words) [view diff] exact match in snippet view article find links to article

context of complexity theory, in which they were used to argue that complexity class separations may face relativization barriers, with the most prominent

Low and high hierarchies (172 words) [view diff] exact match in snippet view article find links to article

to describe the internal structure of the complexity class NP. The low hierarchy starts from complexity class P and grows "upwards", while the high hierarchy

Karp–Lipton theorem (2,269 words) [view diff] exact match in snippet view article find links to article

time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial

Geometric complexity theory (457 words) [view diff] exact match in snippet view article find links to article

science – whether P = NP – by showing that the complexity class P is not equal to the complexity class NP. The idea behind the approach is to adopt and

Postselection (255 words) [view diff] exact match in snippet view article find links to article

order for the postselection to be well-defined. See also PostBQP, a complexity class defined with postselection. Using postselection it seems quantum Turing

Nick Pippenger (415 words) [view diff] exact match in snippet view article find links to article

2013 he became a fellow of the American Mathematical Society. The complexity class, Nick's Class (NC), of problems quickly solvable on a parallel computer

Computational topology (1,591 words) [view diff] exact match in snippet view article find links to article

the problem lies in the complexity class NP. Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP, provided that the

L-reduction (1,017 words) [view diff] exact match in snippet view article find links to article

sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept. Let A and B be optimization problems

Trémaux tree (2,301 words) [view diff] exact match in snippet view article find links to article

trees can be constructed by a randomized parallel algorithm in the complexity class RNC. They can be used to define the tree-depth of a graph, and as part

MAX-3SAT (1,450 words) [view diff] exact match in snippet view article find links to article

number of clauses. MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314). The decision version

Depth-first search (2,437 words) [view diff] exact match in snippet view article find links to article

lexicographic one), can be computed by a randomized parallel algorithm in the complexity class RNC. As of 1997, it remained unknown whether a depth-first traversal

Alan Cobham (mathematician) (329 words) [view diff] exact match in snippet view article

(with Jack Edmonds) inventing the notion of polynomial time and the complexity class P,[B] for Cobham's thesis stating that the problems that have practically

Max/min CSP/Ones classification theorems (1,062 words) [view diff] exact match in snippet view article find links to article

minimize this number. When using the classifications below, the problem's complexity class is determined by the topmost classification that it satisfies. We define

Thomas Jerome Schaefer (177 words) [view diff] exact match in snippet view article find links to article

generalizing Boolean satisfiability in a certain way is either in the complexity class P or is NP-complete. Thomas Jerome Schaefer at the Mathematics Genealogy

Deterministic algorithm (965 words) [view diff] exact match in snippet view article find links to article

theoretically more powerful than those with deterministic output. The complexity class NP (complexity) can be defined without any reference to nondeterminism

Repeat-accumulate code (376 words) [view diff] exact match in snippet view article find links to article

In computer science, repeat-accumulate codes (RA codes) are a low complexity class of error-correcting codes. They were devised so that their ensemble

Equivalence problem (148 words) [view diff] exact match in snippet view article find links to article

Subsequently, the problem was shown to lie in TOWER, the least non-elementary complexity class. It becomes an undecidable problem for pushdown automata or any machine

Polynomial-time counting reduction (753 words) [view diff] exact match in snippet view article find links to article

problem to another) used to define the notion of completeness for the complexity class ♯P. These reductions may also be called polynomial many-one counting

Quantum Turing machine (1,083 words) [view diff] exact match in snippet view article find links to article

polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP. Quantum simulator § Solving physics problems Andrew Yao (1993)

Approximation-preserving reduction (1,497 words) [view diff] exact match in snippet view article find links to article

in what properties they demonstrate on optimization problems (e.g. complexity class membership or completeness, or inapproximability). The different types

Maximal independent set (5,451 words) [view diff] no match in snippet view article find links to article

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other

Sharp-SAT (1,342 words) [view diff] exact match in snippet view article find links to article

sharp P complete). In other words, every instance of a problem in the complexity class #P can be reduced to an instance of the #SAT problem. This is an important

Deterministic context-free language (634 words) [view diff] exact match in snippet view article find links to article

time and O(log2 n) space; as a corollary, DCFL is a subset of the complexity class SC. The set of deterministic context-free languages is closed under

Space complexity (994 words) [view diff] exact match in snippet view article find links to article

problem of whether L = RL. The corresponding nondeterministic space complexity class is NL. The term auxiliary space refers to space other than that consumed

LH (311 words) [view diff] exact match in snippet view article find links to article

fiber LH (complexity) (for "logarithmic hierarchy), a computational complexity class LH (DOS command), a DOS command that loads a program into the upper

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

second-order logic captures precisely the descriptive complexity of the complexity class NP, the class of problems that may be expressed in existential monadic

RNC (214 words) [view diff] exact match in snippet view article find links to article

naked choke, a martial arts move NC (complexity), or RNC, a randomized complexity class in computational complexity theory Nishinippon Broadcasting, a Japanese

DP (849 words) [view diff] exact match in snippet view article find links to article

process DP (complexity), or difference polynomial time, a computational complexity class Data processing Software design pattern, a reusable solution to a common

Skolem arithmetic (1,958 words) [view diff] exact match in snippet view article find links to article

the quantifier-free fragment of Skolem arithmetic belongs to the NP complexity class. Thanks to the above reduction using Feferman–Vaught theorem, we can

FP (530 words) [view diff] exact match in snippet view article find links to article

Iain Banks FP (complexity), in computational complexity theory, a complexity class FP (programming language) designed by John Backus in the 1970s Feature

Average-case complexity (2,746 words) [view diff] exact match in snippet view article find links to article

is not true if P ≠ P#P. A distributional problem (L, D) is in the complexity class AvgP if there is an efficient average-case algorithm for L, as defined

NPI (211 words) [view diff] exact match in snippet view article find links to article

Act) No pun intended Nottingham Prognostic Index NP-intermediate, a complexity class in computational complexity theory Numbering plan indicator Search

ZPL (63 words) [view diff] exact match in snippet view article find links to article

ZPL may refer to: ZPL (complexity), a complexity class ZPL (programming language), for scientific applications Zebra Programming Language, for label printers

QIP (171 words) [view diff] exact match in snippet view article find links to article

rapid innovation, research, and problem solving QIP (complexity), a complexity class in computational complexity theory Quad in-line package, an electronic

RLP (151 words) [view diff] exact match in snippet view article find links to article

wireless (typically cellular) air interface RLP (complexity), the complexity class of problems solvable by a probabilistic machine in logarithmic space

Boson sampling (7,102 words) [view diff] exact match in snippet view article find links to article

in the general case an extremely hard task: it falls in the #P-hard complexity class. Moreover, its approximation to within multiplicative error is a #P-hard

László Babai (1,021 words) [view diff] exact match in snippet view article find links to article

"Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class", J. Comput. Syst. Sci., 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1

MIP (379 words) [view diff] exact match in snippet view article find links to article

Coupled model intercomparison project MIP, an interactive proof system complexity class; see Interactive proof system Mars ISPP Precursor, a test payload intended

FO (457 words) [view diff] exact match in snippet view article find links to article

(IATA airline designator), airline of Argentina FO (complexity), a complexity class .fo, the country code top level domain (ccTLD) for Faroe Islands Fiber

With high probability (383 words) [view diff] exact match in snippet view article find links to article

codes which allow the user to recover the original message WHP. BQP: a complexity class of problems for which there are polynomial-time quantum algorithms

L (disambiguation) (804 words) [view diff] exact match in snippet view article

the p-norm for finite-dimensional vector spaces L (complexity), a complexity class in computational complexity theory L-notation, a notation for running

EH (290 words) [view diff] exact match in snippet view article find links to article

E_{h}} ), a chemical property Exponential hierarchy, a computational complexity class Eh, a spoken interjection in English, Italian, and Spanish ANA Wings

VNP (93 words) [view diff] exact match in snippet view article find links to article

may refer to: VNP, standing for Valiant's NP, an arithmetic circuit complexity class Ventricular Natriuretic Peptide, an alternative name for Brain natriuretic

SZK (80 words) [view diff] exact match in snippet view article find links to article

code for Skukuza Airport Statistical zero knowledge, a computational complexity class introduced by Salil Vadhan Organization of the Kurdish language in

Espace (92 words) [view diff] exact match in snippet view article find links to article

in Wiktionary, the free dictionary. Espace may refer to: ESPACE, a complexity class in computational complexity theory Espace musique, a Canadian radio

Quantum mechanics of time travel (1,572 words) [view diff] exact match in snippet view article find links to article

negentropy and computational power diverge as the noise term goes to zero, complexity class may not be the best way to describe the capabilities of time machines

List of computer scientists (5,134 words) [view diff] exact match in snippet view article find links to article

mobile computing, pervasive computing Walter Savitch – discovery of complexity class NL, Savitch's theorem, natural language processing, mathematical linguistics

AC1 (108 words) [view diff] exact match in snippet view article find links to article

Force between 1919 and 1964 AC1, a candidate phylum of bacteria AC1, a complexity class in circuit complexity AC1 Sentinel, an Australian cruiser tank AC-1

Vaughan Pratt (926 words) [view diff] exact match in snippet view article find links to article

efficiently verified, placing the primality testing problem in the complexity class NP and providing the first strong evidence that the problem is not

Topological sorting (3,176 words) [view diff] exact match in snippet view article find links to article

using a polynomial number of processors, putting the problem into the complexity class NC2. One method for doing this is to repeatedly square the adjacency

Fixed-point logic (2,030 words) [view diff] exact match in snippet view article find links to article

replaced by x and y. Over ordered structures, FO[TC] characterises the complexity class NL. This characterisation is a crucial part of Immerman's proof that

Supertask (2,383 words) [view diff] exact match in snippet view article find links to article

infinity – Concept in the philosophy of mathematics NP (complexity) – Complexity class used to classify decision problems Paradoxes of set theory Transcomputational

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

problem in FNP can be reduced to Π R {\displaystyle \Pi _{R}} . The complexity class of FNP-complete problems is denoted by FNP-C or FNPC. Hence the problem

Differential equations of addition (424 words) [view diff] exact match in snippet view article find links to article

proved that the satisfiability of an arbitrary set of DEA is in the complexity class P when a brute force search requires an exponential time. In 2013,

MENTOR routing algorithm (271 words) [view diff] exact match in snippet view article find links to article

and was published by the IEEE. Empirical observation has shown the complexity class of this algorithm to be O(N²), or quadratic. This represents "a significant

Valiant–Vazirani theorem (520 words) [view diff] exact match in snippet view article find links to article

accepting computation path, thus it belongs to the promise version of the complexity class UP (the class UP as such is only defined for languages). The proof

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

problem is NP-hard. However, if the graph is acyclic, the problem is in complexity class P and can therefore be solved in polynomial time by transforming it

Gödel Prize (2,135 words) [view diff] exact match in snippet view article find links to article

"Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class" (PDF), Journal of Computer and System Sciences, 36 (2): 254–276, doi:10

Savitch's theorem (1,038 words) [view diff] exact match in snippet view article find links to article

nondeterministically in logarithmic space can be solved deterministically in the complexity class L 2 = D S P A C E ( ( log ⁡ n ) 2 ) . {\displaystyle {\mathsf {\color

Ryan Williams (computer scientist) (535 words) [view diff] exact match in snippet view article

Association for Theoretical Computer Science. Williams’s result that the complexity class NEXP is not contained in ACC0 received the best paper award at the

Computability logic (2,560 words) [view diff] exact match in snippet view article find links to article

complete systems characterizing one or another interactive computational complexity class C. This is in the sense that a problem belongs to C if and only if

Ronald Fagin (1,179 words) [view diff] exact match in snippet view article find links to article

thesis, states that existential second-order logic coincides with the complexity class NP in the sense that a decision problem can be expressed in existential

Hypercomputation (3,334 words) [view diff] exact match in snippet view article find links to article

a CTC may allow the rapid solution to PSPACE-complete problems, a complexity class which, while Turing-decidable, is generally considered computationally

L class (231 words) [view diff] exact match in snippet view article find links to article

U.S. Navy L-class star, a type of brown dwarves L (complexity), a complexity class in computational complexity theory L class, indicates "Miscellaneous"

Polyhedral combinatorics (2,304 words) [view diff] exact match in snippet view article find links to article

number k is a computationally difficult problem and complete for the complexity class PP. It is important in the context of cutting-plane methods for integer

Propositional proof system (1,121 words) [view diff] exact match in snippet view article find links to article

Where the bounded arithmetic in turn corresponds to a circuit-based complexity class, there are often similarities between the theory of proof systems and

Amplifier (7,058 words) [view diff] no match in snippet view article find links to article

linear amps, and are used where the power saving justifies the extra complexity. Class-D amplifiers are the main example of this type of amplification. Negative

Folk theorem (game theory) (3,645 words) [view diff] exact match in snippet view article

equilibria for one-shot finite games, a problem which lies in the PPAD complexity class. The practical consequence of this is that no efficient (polynomial-time)

Read-only Turing machine (812 words) [view diff] exact match in snippet view article find links to article

modern research, the model has become important in describing a new complexity class of Quantum finite automata or deterministic probabilistic automata

Digraph realization problem (493 words) [view diff] exact match in snippet view article find links to article

and outdegree b i {\displaystyle b_{i}} . The problem belongs to the complexity class P. Two algorithms are known to prove that. The first approach is given

Linear programming (6,567 words) [view diff] exact match in snippet view article find links to article

linear programming problem was solvable in polynomial time, i.e. of complexity class P. Like the simplex algorithm of Dantzig, the criss-cross algorithm

P class (282 words) [view diff] exact match in snippet view article find links to article

P class or Class P may refer to: P (complexity), a computational complexity class Two classes of steam locomotives used by the New Zealand Railways Department:

Longest path problem (2,662 words) [view diff] exact match in snippet view article find links to article

problem, parameterized by clique-width, is hard for the parameterized complexity class W [ 1 ] {\displaystyle W[1]} , showing that a fixed-parameter tractable

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

Nash equilibrium – Solution concept of a non-cooperative game PP (complexity) – Class of problems in computer science Ukehi – Ancient Japanese ritual using

Bipartite realization problem (610 words) [view diff] exact match in snippet view article find links to article

degree sequence of this bipartite graph. The problem belongs to the complexity class P. This can be proven using the Gale–Ryser theorem, i.e., one has to

Lucas–Lehmer primality test (3,467 words) [view diff] exact match in snippet view article find links to article

is related to the error rate. For constant k, this is in the same complexity class as the Lucas-Lehmer test. In practice however, the cost of doing many

Switching lemma (839 words) [view diff] exact match in snippet view article find links to article

The switching lemma is a key tool used for understanding the circuit complexity class AC0, which consists of constant-depth circuits consisting of AND, OR

S2P (83 words) [view diff] exact match in snippet view article find links to article

File Format, a Touchstone File format for 2-port S-parameters SP 2, a complexity class expressing "symmetric alternation" Microsoft Surface Pro 2, a Surface-series

Nondeterministic finite automaton (4,498 words) [view diff] exact match in snippet view article find links to article

this problem is complete (under parsimonious reductions) for the complexity class SpanL. NFAs and DFAs are equivalent in that if a language is recognized

Well-colored graph (444 words) [view diff] exact match in snippet view article find links to article

Therefore, recognizing non-well-colored graphs can be performed within the complexity class NP. On the other hand, a graph G {\displaystyle G} has Grundy number

Circuit satisfiability problem (1,183 words) [view diff] exact match in snippet view article find links to article

circuit is verifiable in polynomial time. Thus Circuit SAT belongs to complexity class NP. To show NP-hardness, it is possible to construct a reduction from

Hidden-line removal (1,403 words) [view diff] exact match in snippet view article find links to article

work-optimal, but it demonstrates that the hidden-line problem is in the complexity class NC, i.e., it can be solved in polylogarithmic time by using a polynomial

Exponential time hypothesis (3,061 words) [view diff] exact match in snippet view article find links to article

exponential time hypothesis implies that many other problems in the complexity class SNP do not have algorithms whose running time is faster than c n {\displaystyle

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

solvable on n qubits could be solved in poly(n) time, causing the complexity class BQP to be equal to PSPACE. Performing the Hamiltonian simulation, which

Neural cryptography (2,220 words) [view diff] exact match in snippet view article find links to article

Therefore, breaking the security of neural key exchange belongs to the complexity class NP. Alexander Klimov, Anton Mityaguine, and Adi Shamir say that the

Numerical sign problem (2,218 words) [view diff] exact match in snippet view article find links to article

solution of the sign problem would also solve all problems in the complexity class NP in polynomial time. If (as is generally suspected) there are no

Conjunctive query (1,922 words) [view diff] exact match in snippet view article find links to article

data complexity of conjunctive queries is very low, in the parallel complexity class AC0, which is contained in LOGSPACE and thus in polynomial time. The

Quantum contextuality (5,898 words) [view diff] exact match in snippet view article find links to article

compute linear Boolean functions, i.e. to solve problems in the Parity L complexity class ⊕L. For interactions with multi-qubit quantum systems a natural assumption

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

of graph isomorphism. However, it has been shown to belong to the complexity class AM. Additionally, testing whether the distinguishing chromatic number

Space hierarchy theorem (2,699 words) [view diff] exact match in snippet view article find links to article

complexity of (nondeterministic) linear bounded automata which accept the complexity class N S P A C E ( n ) {\displaystyle {\mathsf {NSPACE}}(n)} (aka as context-sensitive

Newton's identities (7,642 words) [view diff] exact match in snippet view article find links to article

and solving a triangular system of equations. Both can be done in complexity class NC (solving a triangular system can be done by divide-and-conquer)

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

by slopes, is complete for the existential theory of the reals, a complexity class at least as difficult as being NP-complete. As well as being related

Steiner tree problem (4,365 words) [view diff] exact match in snippet view article find links to article

Euclidean Steiner tree problem is NP-complete, since membership to the complexity class NP is not known. The rectilinear Steiner tree problem is a variant

Exact division (5,997 words) [view diff] exact match in snippet view article find links to article

An adaptation of this algorithm shows that the problem is in the complexity class PPA. This holds even for arbitrary bounded and non-atomic valuations

Quantum refereed game (3,254 words) [view diff] exact match in snippet view article find links to article

in QRG. This probability is ≥ 1-ε. More formally, QRG denotes the complexity class for all promise problems having quantum refereed games defined as follows

Clique problem (9,876 words) [view diff] exact match in snippet view article find links to article

implies that the problem is unlikely to be solvable within the parallel complexity class NC. One can test whether a graph G contains a k-vertex clique, and

Metric dimension (graph theory) (2,505 words) [view diff] exact match in snippet view article

metric dimension decision problem is complete for the parameterized complexity class W[2], implying that a time bound of the form nO(k) as achieved by this

Berlekamp switching game (1,968 words) [view diff] exact match in snippet view article find links to article

guarantees. A different derandomization gives a parallel algorithm in the complexity class NC. Finding the optimal choice for the second player in the game, once

Indistinguishability obfuscation (2,086 words) [view diff] exact match in snippet view article find links to article

Additionally, if iO and one-way functions exist, then problems in the PPAD complexity class are provably hard. However, indistinguishability obfuscation cannot

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

polynomial contains negative terms, which places the problem in the complexity class GapP, the closure of #P under subtraction. To accommodate rational

Blichfeldt's theorem (1,935 words) [view diff] exact match in snippet view article find links to article

to Blichfeldt's theorem has been shown to be complete for the PPP complexity class, and therefore unlikely to be solvable in polynomial time. The problem

Feedback arc set (6,071 words) [view diff] exact match in snippet view article find links to article

problem, the case of tournaments, the problem remains NP-complete. The complexity class APX is defined as consisting of optimization problems that have a polynomial

Group testing (9,937 words) [view diff] exact match in snippet view article find links to article

testing has not been determined, it is suspected to be hard in some complexity class. However, an important breakthrough occurred in 1972, with the introduction

Quadratic knapsack problem (3,911 words) [view diff] exact match in snippet view article find links to article

greatest contribution. Repeat until there is no improving swapping. The complexity class of this algorithm is O ( 2 n ) {\displaystyle O(2^{n})} since for the