FOM: Additions on a version of Bounded Arithmetic

Vladimir Sazonov sazonov at
Mon Oct 5 10:11:19 EDT 1998

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 

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

More information about the FOM mailing list