[FOM] Kolmogorov Feasibility??

[V.Sazonov@csc.liv.ac.uk]

Quoting Mirco Mannucci <mmannucc at cs.gmu.edu> Mon, 10 Jul 2006:

> Dear FOM Fellows,
>
> though I am convinced that the notion of feasibility should be
> investigated as a primitive one, either as a unary or n-ary predicate (in
> case one wishes to consider relative feasibility ), I think it is also
> worth trying to model it in some concrete way.
>
> In this spirit, it recently occurred to me that, as numbers can be
> realized as binary strings,

I think that this fact is insufficient for identification the natural 
numbers - genuine unary objects - with binary strings. This is only a 
convenient technical tool for short notation system. On the other hand, 
binary strings *considered as strings* are indeed important finite 
objects to be considered in the context of "feasibility".


one could come up with the following: a number
> is feasible iff its algorithmic complexity as a string is small (with respect
> to the number itself).


Again, how to understand "the number itself" here? The context of 
feasibility is sufficiently subtle one and we need to make clear 
difference which is also done in complexity theory. It is only if 
complexity questions are ignored, the difference between unary and 
binary representation of numbers is considered as irrelevant. By "the 
number itself" I would rather understand its unary representation.


>
> By complexity here I mean Kolmogorov complexity, or some related
> concept.


The "mesure" of complexity is eventually reduced to the length of 
(codes) of strings. So, the right primitive and fundamental concept of 
feasibility is that of unary or binary string of *feasible length* - 
shortly - feasible string. Then feasible number should be rather 
understood as feasible unary string. I believe that this terminological 
and conceptual clarification is crucial one for considerations on 
feasibility.

I also believe that the proper framework for formalisation of 
feasibility is axiomatic one assuming also weakening the underlying 
logic. The first approximation to feasibility is via weak theories of 
arithmetic (known as versions of Bounded Arithmetic) or weak theories 
of binary strings (even in the framework of the ordinary classical 
logic) where exponential is not provably total operation and where, 
therefore, the "difference" between unary and binary strings becomes 
formalised as "infinite". It is not just complex (difficult) to 
transform binary to unary, but, in general, impossible. However, 
formalising the genuine feasibility where even the transformation of 
binary strings of the length, say, 1000 to unary strings is postulated 
as impossible (2^1000 is considered as the infinity) requires some 
changes in logic to be formally consistent. The main idea is that the 
traditional abbreviating mechanisms (for terms, but not necessarily for 
formulas) implicitly formalised in contemporary logical systems via, 
say, cut rule + quantifier rules should be restricted in that or other 
way.  When we introduce an existential quantifier and later on 
eliminate it we use an abbreviation of a term by the quantified 
variable; this way the existence of "forbidden" non-feasible (or of 
non-feasibly complex) finite objects can be derived giving rise to 
formal contradiction, say, with the postulated infinity of 2^1000.


>
> Any such notion of "Kolmogorov feasibility" would not be monotonic, but
> after all, who said it should be?
>
> Now my question: is there any ref to the above? And, if so, who has worked
> on this approach  or similar ones?


I think you will find some closely related material in my old papers.

* In the framework exists n 2^n = infinity:

1. A logical approach to the problem "P=?NP", in: MFCS'80, Lecture 
Notes in Computer Science, N88, Springer, New York, 1980, P.562-575. 
Available online http://www.csc.liv.ac.uk/~sazonov/papers/MFCS80.pdf

(An important correction to this paper is given in [On existence of 
complete predicate calculus in metamathematics without exponentiation, 
MFCS'81, Lecture Notes in Computer Science, N118, Springer, New York, 
1981, P.483--490.], P.490.)

2. An equivalence between polynomial constructivity of Markov's 
principle and the equality P=NP, Siberian Advances in Mathematics, 
1991, v.1, N4, pp. 92-121 (English translation of a paper in Russian 
published in Matematicheskaja logika i algoritmicheskie problemy, Trudy 
Instituta matematiki SO AN SSSR, 12, Novosibirsk, ``Nauka'', Sibirskoe 
otdelenie, 1989, pp. 138--165.)

A hardcopy is available by request.

Here complexity of binary strings is measured relatively to so called 
polynomially optimal unary (whereas Kolmogorov considered additively 
optimal binary) encoding.

* In the framework 2^1000 = infinity with a restriction on logic:

3. On Feasible Numbers, in: Leivant D., ed., Logic and Computational 
Complexity, LNCS Vol. 960, Springer, 1995, pp.30--51.
Available online http://www.csc.liv.ac.uk/~sazonov/papers/lcc.ps
(See also a short exposition in 
http://www.cs.nyu.edu/pipermail/fom/2006-February/009746.html)

Especially see Section 6 for a comment on bounded quantifiers and the 
existence or non-existence of complex binary strings of feasible 
length. This topic is actually considered in all the above papers and 
is closely related with the problem P=?NP.


Vladimir Sazonov


----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.