First-order reduction and computational complexity

DOI10.3969/J.ISSN.1006-6330.2015.04.006MaRDI QIDQ2994065zbMATH OpenFDO

Authors Shuliang Bai, Manyem Prabhu

Publication date 10 August 2016

Full work available at URL https://doi.org/10.3969/J.ISSN.1006-6330.2015.04.006

zbMATH Keywords

computational complexitydescriptive complexitylogical reductionlogical sentence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 408812
• scientific article; zbMATH DE number 3936520
• Methods for proving completeness via logical reductions
• Logics for complexity classes
• On completeness for NP via projection translations

Cited in

(4)

• Computational depth and reducibility
• scientific article; zbMATH DE number 1722667 (Why is no real title available?)
• Reductional programming of functions represented by recurrent relations of the first order
• Inductive Logic Programming

This page was built for publication: First-order reduction and computational complexity

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