Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Semicomputable function (view), Log-space computable function (view)

searching for Computable function 38 found (426 total)

FL (complexity) (273 words) [view diff] no match in snippet view article

In computational complexity theory, the complexity class FL is the set of function problems which can be solved by a deterministic Turing machine in a

Speedup theorem (105 words) [view diff] exact match in snippet view article find links to article

constant factor. Blum's speedup theorem, which provides speedup by any computable function (not just linear, as in the previous theorem). Amdahl's law, the

Rice–Shapiro theorem (3,454 words) [view diff] exact match in snippet view article find links to article

{\displaystyle \phi } ) is semi-decidable. Then for any partial computable function f {\displaystyle f} , it holds that P {\displaystyle P} contains

Termination analysis (1,730 words) [view diff] exact match in snippet view article find links to article

difficult than the halting problem. Now as the question whether a computable function is total is not semi-decidable, each sound termination analyzer (i

Cylindric numbering (168 words) [view diff] exact match in snippet view article find links to article

\nu } is reducible to μ {\displaystyle \mu } then there exists a computable function f {\displaystyle f} with ν = μ ∘ f {\displaystyle \nu =\mu \circ

Sudan function (550 words) [view diff] exact match in snippet view article find links to article

Ackermann function. In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm

Oblivious transfer (2,019 words) [view diff] exact match in snippet view article find links to article

transfer it is possible to securely evaluate any polynomial time computable function without any additional primitive. In Rabin's oblivious transfer protocol

Ludics (489 words) [view diff] exact match in snippet view article find links to article

For example, a realizer for the proposition "A implies B" is a computable function that takes a realizer for A, and uses it to compute a realizer for

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

⋅ | x | O ( 1 ) {\displaystyle f(k)\cdot {|x|}^{O(1)}} for some computable function f. Typically, this function is thought of as single exponential,

Reduction (computability theory) (1,982 words) [view diff] exact match in snippet view article

{\displaystyle A} is many-one reducible to B {\displaystyle B} if there is a computable function f {\displaystyle f} with A ( x ) = B ( f ( x ) ) {\displaystyle A(x)=B(f(x))}

Basis theorem (computability) (652 words) [view diff] exact match in snippet view article

{\displaystyle X} -computable function f : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} } is dominated by a total computable function g {\displaystyle

Pointclass (1,070 words) [view diff] exact match in snippet view article find links to article

\Sigma _{1}^{0}} set has at least one index, which describes the computable function enumerating the basic open sets from which it is composed; in fact

Kőnig's lemma (2,344 words) [view diff] exact match in snippet view article find links to article

is called computably bounded or recursively bounded if there is a computable function f {\displaystyle f} from ω {\displaystyle \omega } to ω {\displaystyle

PLS (complexity) (5,471 words) [view diff] exact match in snippet view article

F_{L}(I)} are polynomial time verifiable There is a polynomial time computable function A : D L → F L ( I ) {\displaystyle A:D_{L}\rightarrow F_{L}(I)} that

Monochromatic triangle (481 words) [view diff] exact match in snippet view article find links to article

vertices of the input graph multiplied by a quickly-growing but computable function of the treewidth. Garey, Michael R.; Johnson, David S. (1979), Computers

Manifest expression (264 words) [view diff] exact match in snippet view article find links to article

affine) in its variables. A manifest expression is a compile time computable function which depends only on compile-time constants, manifest variable references

Emil Leon Post (1,408 words) [view diff] exact match in snippet view article find links to article

canonically represent any Post-generative language, and indeed any computable function or set at all. Correspondence systems were introduced by Post in

PPAD (complexity) (1,003 words) [view diff] exact match in snippet view article

at most one successor. G is specified by giving a polynomial-time computable function f(v) (polynomial in the size of v) that returns the predecessor and

Caterpillar tree (1,205 words) [view diff] exact match in snippet view article find links to article

algorithm for the MSCP unless P = NP. Here f(n) is any polynomial-time computable function of n, the number of vertices of a graph. There is a parametrized

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

{\displaystyle L} , the size of x ′ {\displaystyle x'} is bounded by a computable function f {\displaystyle f} in k {\displaystyle k} , and k ′ {\displaystyle

Disjunction and existence properties (1,178 words) [view diff] exact match in snippet view article find links to article

natural number e such that, letting f e {\displaystyle f_{e}} be the computable function with index e, the theory proves ( ∀ x ) φ ( x , f e ( x ) ) {\displaystyle

Disjunction and existence properties (1,178 words) [view diff] exact match in snippet view article find links to article

natural number e such that, letting f e {\displaystyle f_{e}} be the computable function with index e, the theory proves ( ∀ x ) φ ( x , f e ( x ) ) {\displaystyle

Brainfuck (1,884 words) [view diff] exact match in snippet view article find links to article

Turing-complete language, Brainfuck is theoretically capable of computing any computable function or simulating any other computational model if given access to an

Process calculus (2,452 words) [view diff] exact match in snippet view article find links to article

various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing machines and the lambda calculus

Generic property (1,640 words) [view diff] exact match in snippet view article find links to article

as an element; No 1-generic is computable (or even bounded by a computable function); All 1-generics f {\displaystyle f} are generalised low: f ′ ≡ T

Parsimonious reduction (1,084 words) [view diff] exact match in snippet view article find links to article

that map bounded parameter values to bounded parameter values by a computable function. Polynomial-time parsimonious reductions are a special case of a

Integer programming (4,185 words) [view diff] exact match in snippet view article find links to article

a {\displaystyle a} and d {\displaystyle d} . That is, for some computable function f {\displaystyle f} and some constant k {\displaystyle k} , integer

Combinatory logic (5,295 words) [view diff] exact match in snippet view article find links to article

equal to any lambda term, and therefore, by Church's thesis, to any computable function whatsoever. The proof is to present a transformation, T[ ], which

Large numbers (7,427 words) [view diff] exact match in snippet view article find links to article

function Σ is an example of a function which grows faster than any computable function. Its value for even relatively small input is huge. The values of

K-trivial set (1,837 words) [view diff] exact match in snippet view article find links to article

set. In the context of computability theory, a cost function is a computable function c : N × N → Q ≥ 0 . {\displaystyle c:\mathbb {N} \times \mathbb {N}

Polynomial creativity (1,742 words) [view diff] exact match in snippet view article find links to article

{NP} ^{(k)}} . More formally, there should exist a polynomially computable function f {\displaystyle f} that maps programs in this class to inputs on

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

all Turing machines. If F is a subset of the set of all partial computable function from N {\displaystyle \mathbb {N} } to itself such that F and its

APL (programming language) (9,838 words) [view diff] exact match in snippet view article

all versions of APL, it is theoretically possible to express any computable function in one expression, that is, in one line of code.[citation needed]

Algorithmically random sequence (4,904 words) [view diff] exact match in snippet view article find links to article

known as weakly computable, lower semi-computable) if there exists a computable function d ^ : { 0 , 1 } ∗ × N → Q {\displaystyle {\widehat {d}}:\{0,1\}^{*}\times

Complexity class (10,382 words) [view diff] exact match in snippet view article find links to article

a problem Y {\displaystyle Y} if there exists a polynomial-time computable function p {\displaystyle p} such that for all x ∈ Σ ∗ {\displaystyle x\in

Intersection number (graph theory) (4,363 words) [view diff] exact match in snippet view article

by a polynomial in n {\displaystyle n} multiplied by a larger but computable function of the intersection number k {\displaystyle k} . This may be shown

Twin-width (4,053 words) [view diff] exact match in snippet view article find links to article

{\displaystyle O(n^{c}\,f(k))} for some constant c {\displaystyle c} and computable function f {\displaystyle f} . For instance, a running time of O ( n 2 k )

Fine and Wilf's theorem (2,424 words) [view diff] exact match in snippet view article find links to article

other letters. The following has been proved: Theorem—There exists a computable function L ( h , p , q ) {\displaystyle L(h,p,q)} such that, if a word w