Towards theories for positive polynomial time and monotone proofs with extension

## Author: Anupam Das

## Paper Information

Title: | Towards theories for positive polynomial time and monotone proofs with extension |

Authors: | Anupam Das |

Proceedings: | PC Abstracts |

Editors: | Jan Johannsen and Olaf Beyersdorff |

Keywords: | Monotone complexity, Monotone proofs, Bounded arithmetic, Equational theories, Intuitionistic logic, Witnessing |

Abstract: | ABSTRACT. We propose arithmetic theories that link systems in monotone proof complexity to classes in monotone computational complexity. In particular, we focus on the case of polynomial-time, for which monotone function classes and monotone proof systems have recently been proposed. We complete the proof complexity theoretic account of this subject by proposing an accompanying logical theory, in the usual sense of 'bounded arithmetic' |

Pages: | 3 |

Talk: | Jul 08 15:00 (Session 41) |

Paper: |