Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: List of complexity classes (view)

searching for Complexity class 113 found (315 total)

Parameterized complexity (2,684 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,398 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

Stephen Cook (1,540 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,773 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,273 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 (472 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

General recursive function (2,747 words) [view diff] exact match in snippet view article find links to article

values in {0,1} is known in computational complexity theory as the complexity class R. The μ-recursive functions (or general recursive functions) are partial

Nick Pippenger (416 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

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,449 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

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

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

Michael O. Rabin) inventing the notion of polynomial time and the complexity class P,[B] for Cobham's thesis stating that the problems that have practically

Atlantic City algorithm (156 words) [view diff] case mismatch in snippet view article find links to article

Atlantic City algorithm is a probabilistic polynomial time algorithm (PP Complexity Class) that answers correctly at least 75% of the time (or, in some versions

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

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 (375 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

Computational topology (1,567 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

Quantum Turing machine (1,105 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)

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

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

Deterministic context-free language (633 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

Sharp-SAT (1,495 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

Space complexity (1,004 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

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

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

Center of Paraguay (CORP), a Paraguayan trade union federation co-RP, a complexity class of computational complexity theory closely related to RP (complexity)

List of unsolved problems in computer science (1,175 words) [view diff] exact match in snippet view article find links to article

solvable in polynomial time. This uncertainty places it in a unique complexity class, making it a significant open problem in computer science. Is graph

Skolem arithmetic (1,957 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

DP (833 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

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

raster file format for nautical charts RNC, a randomized computational complexity class extending NC Nishinippon Broadcasting, a Japanese commercial broadcaster

LH (341 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

Average-case complexity (2,834 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

László Babai (1,022 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

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

FP (546 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

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

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

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

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

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

L (disambiguation) (810 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

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

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

determine a material's porous structure MIP, an interactive proof system complexity class; see Interactive proof system Minimum ionizing particle, in particle

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

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

List of computer scientists (5,229 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

EH (300 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

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

Ryan Williams (computer scientist) (545 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

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

Topological sorting (3,170 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,386 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,174 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,

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

Gödel Prize (2,163 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

MENTOR routing algorithm (274 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

Path cover (446 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

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

Hypercomputation (3,368 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

Savitch's theorem (1,094 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

1-vs-2 cycles problem (421 words) [view diff] exact match in snippet view article find links to article

the number of rounds for this problem would imply that the parallel complexity class NC1 does not contain all problems in polynomial time, which would be

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

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"

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,112 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. A

Folk theorem (game theory) (3,650 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

Flipism (2,112 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

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:

Linear programming (6,690 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

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

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

Lucas–Lehmer primality test (3,518 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, and is similarly fast in practice. The most

Bipartite realization problem (611 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

Switching lemma (869 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

Constraint satisfaction problem (3,355 words) [view diff] exact match in snippet view article find links to article

all first-order reducts of all unary structures, all CSPs in the complexity class MMSNP. Most classes of CSPs that are known to be tractable are those

Nondeterministic finite automaton (4,499 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

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

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

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

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

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

Quantum contextuality (5,857 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

HHL algorithm (4,990 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

Numerical sign problem (2,260 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

Space hierarchy theorem (2,784 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

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

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

Newton's identities (7,644 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)

Steiner tree problem (4,391 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

Consensus splitting (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

Clique problem (9,905 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

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

Metric dimension (graph theory) (2,520 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

Indistinguishability obfuscation (2,298 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

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

Tutte polynomial (5,377 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,130 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,934 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

Yao's principle (3,761 words) [view diff] exact match in snippet view article find links to article

{2}{3}}} ); this condition together with polynomial time defines the complexity class BQP. It does not make sense to ask for deterministic quantum algorithms

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

Fibonacci anyons (3,370 words) [view diff] exact match in snippet view article find links to article

First, one is given an instance of a decision problem which is in the complexity class BQP (for instance, a large integer whose factorization one wishes to