Nested PLS

DOI10.1007/S00153-010-0221-8MaRDI QIDQ535153zbMATH OpenOpenAlexFDO

Authors Toshiyasu Arai

Publication date 11 May 2011

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 2196511 (Why is no real title available?)
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Characterising definable search problems in bounded arithmetic via proof notations
• How easy is local search?
• NP search problems in low fragments of bounded arithmetic
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic

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)