Classification of search problems and their definability in bounded arithmetic

Tsuyoshi Morioka

TSpace · 2001 · 13 citations · 0 references

Full text

Open access

Concepts

Abstract

We present a new framework for the study of search problems and their definability in bounded arithmetic. We identify two notions of complexity of search problems: verification complexity and computational complexity. Notions of exact solvability and exact reducibility are developed, and exact b i -definability of search problems in bounded arithmetic is introduced. We specify a new machine model called the oblivious witness-oracle Turing machines. Based on