Loading...
Please wait, while we are loading the content...
Similar Documents
Improved witnessing and local improvement principles for second-order bounded arithmetic (2012).
| Content Provider | CiteSeerX |
|---|---|
| Author | Beckmann, Arnold Buss, Samuel R. |
| Abstract | ThispaperconcernsthesecondordersystemsU 1 2 andV1 2 ofbounded arithmetic, whichhaveprooftheoreticstrengthscorrespondingtopolynomial space and exponential time computation. We formulate improved witnessing theorems for these two theories by using S1 2 as a base theory for proving the correctness of the polynomial space or exponential time witnessing functions. We develop the theory of nondeterministic polynomial space computation in U1 2. Kolodziejczyk, Nguyen, and Thapen have introduced local improvement properties to characterize the provably total NP functions of these second order theories. We show that the strengths of their local improvement principles over U1 1 2 and V2 depend primarily on the topology of the underlying graph, not the number of rounds in the local improvement games. ThetheoryU 1 2 provesthelocalimprovementprincipleforlinear graphs even without restricting to logarithmically many rounds. The local improvement principle for grid graphs with only logarithmically rounds is complete for the provably total NP search problems of V 1 2. Related results are obtained for local improvement principles with one improvement round, and for local improvement over rectangular grids. The authors thank the John Templeton Foundation for supporting their participation |
| File Format | |
| Publisher Date | 2012-01-01 |
| Access Restriction | Open |
| Subject Keyword | Local Improvement Principle Second-order Bounded Arithmetic Provably Total Np Search Problem Underlying Graph Polynomial Space Base Theory Local Improvement Property Witnessing Theorem Local Improvement Game Exponential Time Exponential Time Computation John Templeton Foundation Local Improvement Nondeterministic Polynomial Space Computation Grid Graph Second Order Theory Many Round Provably Total Np Function Rectangular Grid Improvement Round |
| Content Type | Text |
