Some simplified undecidable and NP-hard problems for simple programs

DOI10.1016/0304-3975(82)90131-1MaRDI QIDQ1157168zbMATH OpenOpenAlexFDO

Authors Eitan M. Gurari, Oscar H. Ibarra

Publication date 1982

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(82)90131-1

zbMATH Keywords

NP-completenessundecidabilityequivalence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of software (68N99)

Cites work

• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• A Complete and Consistent Hoare Axiomatics for a Simple Programming Language
• Even Simple Programs Are Hard To Analyze
• On the Computational Complexity of Program Scheme Equivalence
• Reducibility among combinatorial problems
• Subrecursive Programming Languages, Part I
• The Complexity of Finite Memory Programs with Recursion
• The Complexity of the Equivalence Problem for Simple Programs
• The Equivalence Problem of Simple Programs
• The complexity of theorem-proving procedures

Cited in

(1)

• On the zero-inequivalence problem for loop programs

This page was built for publication: Some simplified undecidable and NP-hard problems for simple programs

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