FOM: Additions on a version of Bounded Arithmetic

[Vladimir Sazonov]

In my last posting I described very roughly some features
of a version of Bounded Arithmetic. In particular, it was
stated existence of several bijections. It should be noted
additionally that all these bijections are computable! 
Moreover, they are consequences of one of them:

	a fixed polynomial time computable bijection from
	finite unary strings to finite binary strings 
	(by means of this bijection all binary strings are 
	"constructible")

and also of an additional postulate (which makes existence 
of the above bijection a non-banality) 

not EXP:   	exists number n such that 
		for all finite binary strings x 

			log|x| < n

holds where log is base 2 logarithm and |x| denotes the length 
of a string x. 

Cf. details in my paper "A logical approach to the problem P=NP?" 
in Lecture  Notes  in  Computer  Science,  N88 (1980) 
and a correction  in LNCS 118 (1981) on page 490.


Vladimir Sazonov