FOM: Additions on a version of Bounded Arithmetic
sazonov at logic.botik.ru
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.
More information about the FOM