First-order reduction and computational complexity

DOI10.3969/J.ISSN.1006-6330.2015.04.006zbMATH Open1349.68100MaRDI QIDQ2994065FDOQ2994065

Authors: Shuliang Bai, Manyem Prabhu 

Publication date: 10 August 2016

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

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)

Cited In (4)

• Computational depth and reducibility
• Title not available (Why is that?)
• 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)