Some simplified undecidable and NP-hard problems for simple programs

DOI10.1016/0304-3975(82)90131-1zbMath0469.68051OpenAlexW1972615345MaRDI QIDQ1157168

Oscar H. Ibarra, Eitan M. Gurari

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

undecidabilityNP-completenessequivalence problem

Mathematics Subject Classification ID

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

Related Items (1)

On the zero-inequivalence problem for loop programs

Cites Work

• Unnamed Item
• On the Computational Complexity of Program Scheme Equivalence
• The Complexity of the Equivalence Problem for Simple Programs
• Even Simple Programs Are Hard To Analyze
• The Complexity of Finite Memory Programs with Recursion
• A Complete and Consistent Hoare Axiomatics for a Simple Programming Language
• Reducibility among Combinatorial Problems
• The Equivalence Problem of Simple Programs
• The complexity of theorem-proving procedures
• Subrecursive Programming Languages, Part I

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