Logic in Computer Science (LICS 2004)

Invited Talk: Feasible Proofs and Computations: Partnership and Fusion (at LICS 2004)

Authors: Alexander A. Razborov

Abstract

A computation or a proof is called feasible if it obeys prescribed bounds on the resources consumed during its execution. It turns out that when restricted to this world of feasibility, proofs and computations become extremely tightly interrelated, sometimes even indistinguishable. Moreover, many of these rich relations, underlying concepts, techniques etc. look very different from their "classical" counterparts, or simply do not have any. This talk is intended as a very informal and popular (highly biased as well) attempt to illustrate these fascinating connections by several related developments in the modern complexity theory.

BibTeX

  @InProceedings{Razborov-FeasibleProofsandCo,
    author = 	 {Alexander A. Razborov},
    title = 	 {Feasible Proofs and Computations: Partnership and Fusion},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2004},
    year =	 2004,
    editor =	 {Harald Ganzinger},
    month =	 {July}, 
    pages =      {134--138},
    location =   {Turku, Finland}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}
  }