Nested PLS

DOI10.1007/S00153-010-0221-8zbMATH Open1232.03052arXiv1005.2005OpenAlexW2915010390MaRDI QIDQ535153FDOQ535153

Authors: Toshiyasu Arai 

Publication date: 11 May 2011

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Abstract: In this note we will introduce a class of search problems, called nested Polynomial Local Search (nPLS) problems, and show that definable NP search problems, i.e., $Sigm{a}_1^b$-definable functions in $T_2^2$ are characterized in terms of the nested PLS.

Full work available at URL: https://arxiv.org/abs/1005.2005

Recommendations

• On Search Problems in Complexity Theory and in Logic (Abstract)
• A note on the complexity of local search problems
• Characterising definable search problems in bounded arithmetic via proof notations
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• scientific article; zbMATH DE number 6783433

zbMATH Keywords

bounded arithmeticsearch problemsnested recursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Characterising definable search problems in bounded arithmetic via proof notations
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• NP search problems in low fragments of bounded arithmetic
• Title not available (Why is that?)

This page was built for publication: Nested PLS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q535153)