Publication:2978535

DOI10.4230/LIPIcs.FSTTCS.2014.445zbMath1360.68482MaRDI QIDQ2978535

A. Pavan, Debasis Mandal, Rajeswari Venugopalan

Publication date: 25 April 2017

zbMATH Keywords

NP-completeness; Turing completeness; Cook reduction; many-one completeness; Karp reduction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)