Find link

language:

Find link is a tool written by Edward Betts.

searching for Polynomial-time reduction 9 found (26 total)

alternate case: polynomial-time reduction

Light Up (puzzle) (778 words) [view diff] exact match in snippet view article

Light Up puzzle is solvable is NP-complete. This is proved by a polynomial-time reduction from Circuit-SAT, which is known to be NP-complete, to Light Up

Ring learning with errors (2,978 words) [view diff] exact match in snippet view article find links to article

version of the shortest vector problem (SVP) in a lattice (a polynomial-time reduction from this SVP problem to the RLWE problem has been presented)

Set packing (1,518 words) [view diff] exact match in snippet view article find links to article

problem is also equivalent to set packing – there is a one-to-one polynomial-time reduction between them: Given a set packing problem on a collection S {\displaystyle

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

parameter k is said to admit a linear vertex kernel if there is a polynomial time reduction, called a kernelization algorithm, that maps the input instance

Regular language (3,414 words) [view diff] exact match in snippet view article find links to article

and is in fact complete for exponential space with respect to polynomial-time reduction. For a fixed finite alphabet, the theory of the set of all languages

Token reconfiguration (1,220 words) [view diff] exact match in snippet view article find links to article

elements (the latter of which is notably a constant). So we have a polynomial-time reduction from set cover, which is NP-complete, to token reconfiguration

Learning with errors (3,418 words) [view diff] no match in snippet view article find links to article

{\displaystyle n} . Peikert proves that there is a probabilistic polynomial time reduction from the GapSVP ζ , γ {\displaystyle \operatorname {GapSVP} _{\zeta

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

bounded halting problem. Theorem 4 There is a notion of generic-polynomial-time reduction with respect to which the distributional bounded halting problem

Homomorphic signatures for network coding (3,297 words) [view diff] no match in snippet view article find links to article

r}(a_{i}P_{i})=\sum _{1\leq j\leq r}(b_{j}P_{j}).} Proposition: There is a polynomial time reduction from discrete log on the cyclic group of order p {\displaystyle