yet more primes

[Richard Guy]

MR1106666 (93d:03046)
Jones, J. P.(3-CALG); Matijasevich, Y. V.(RS-AOS2)
Basis for the polynomial time computable functions.
Number theory (Banff, AB, 1988), 255--270,
de Gruyter, Berlin, 1990.
03D20 (03D15 11Y16)
								  	
References: 0 	Reference Citations: 0 	Review Citations: 0
A basis for a class of functions is a finite set of functions sufficient 
to generate the entire class under composition. A proof of the fact that 
PF, the class of polynomial time computable functions, has a basis is 
given. The result is due to A. A. Muchnik, but it appeared in an almost 
unknown paper of his \ref[in Problems of mathematical logic (Russian), 
123--138, "Mir", Moscow, 1970; RZhMat 1971:4 A45]. In the present paper it 
is shown that there exists a basis consisting of only one function. If 
only one-variable functions are allowed, two functions are necessary and 
sufficient to form a basis of PF. Some possible implications for the 
$\roman P{\overset?\to=}{\rm NP}$ problem are discussed.

{For the entire collection see MR 92a:11001.}

Reviewed by Marius Zimand


On Wed, 3 Dec 2003, Jon Awbrey wrote:

> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> 
> didn't there used to be something like
> a 26 variable logical formula that
> defines primes?
> 
> 2 lazy 2 look r up,
> 
> ja
> 
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>