Browse Prior Art Database

Some Simplified Undecidable and NP-hard Problems for Simple Programs

IP.com Disclosure Number: IPCOM000128555D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 32 page(s) / 65K

Publishing Venue

Software Patent Institute

Related People

Eitan M. Gurari: AUTHOR [+4]

Abstract

The complexity of the equivalence problem for several classes of simple programs with a fixed number of program variables is investigated. The classes are shown to have undecidable, NP-hard, or polynomial-time decidable equivalence problem.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 32

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Some Simplified Undecidable and NP-hard Problems for Simple Programs

by Eitan M. Gurari and Oscar H. Ibarra

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota. 55455 Technical Report 7924 October 1979 Cover design courtesy of Ruth and Jay Leavitt. Some Simplified Undecidable and NP-hard Problems for Simple Programs*

by

Eitan M. Gurarit Department of Electrical Engineering and Computer Science University of Wisconsin-Milwaukee Milwaukee, WI 53201 and

Oscar H. Ibarra Department of Computer Science University of Minnesota Minneapolis, MN 55455

Abstract

The complexity of the equivalence problem for several classes of simple programs with a fixed number of program variables is investigated. The classes are shown to have undecidable, NP- hard, or polynomial-time decidable equivalence problem. A' ,a

* This research was supported by NSF Grants MCS78-01736 and MCS79-09967.

Part of this research was done while the author was at the University of Minnesota.

1. Introduction

The equivalence problem is known to be intractable or undecidable even for programs written in very simple programming languages [eg., 2, 5,7,8]. For example, the inequivalence problem is NP-complete [3,6] for Ll programs [2,9] while the equivalence problem is undecidable for L2 programs [1]. (For i > 0, Li is the loop language consisiting only of

instructions:

(Equation Omitted)

with at most i levels of do nestings [7].) On the other hand, the equivalence problem is decidable in polynomial time for LO programs [9]. As another example, the halting problem (and hence also the equivalence problem) is undecid-able for programs that are restricted to instructions of the form

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 32

Some Simplified Undecidable and NP-hard Problems for Simple Programs

then go to Q, and RotG Q [8]. The last result holds even when the programs are allowed to use only two variables [8]. Thevresults of this paper are along this line, i.e., we consider several classes of simple programs with a fixed number of program variables. The classes are shown to have undecidable, NP-hard (see [3 ,6] for definition and motivations), or polynomial-time decidable equivalence problem.

Consider the programming language XL which has the following instruc- tion set _

(Equation Omitted)

(Equation Omitted)

An XL program P is any finite nonempty sequence of instructions of the form (1) - (8) satisfying the following conditions: (R1) _d4 .. end pairs only enclose instructions of the form (1) - (3)and (- 5)- (8T-. Thus, nested do's are not permitted. (R2) Labels in instructions of the form (7) - (8) are forward labels. (R3) No instruction in the scope of a do ... end construct can be labeled. (The do itself can be labeled,)

Each program variable can hold any nnnnegative integer. The variable x controlling the do x ... _end constr...