Browse Prior Art Database

P-Complete Problems and Approximate Solutions

IP.com Disclosure Number: IPCOM000128519D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 26K

Publishing Venue

Software Patent Institute

Related People

Sartaj Sahni: AUTHOR [+4]

Abstract

We study the class of P-Complete problems and show the folloc~7ings i) for any constant s > 0 there is a P-complete problem for which an s-approximate solution can be found in linear time ii) there exist P-Complete problems far which linear time approximate solutions that get closer and closer to the optimal (with increasing problem size) can he found iii) there exist P-Complete problems for which the approximation problems are also P-Complete. Key Words: P-Complete, approximation, algorithm, polynomial complexity, Iz-Partition, I:-TZaxCut This research was supported by University of r?3nnesota Research Grant 1/481-006-4125-02.

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

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

P-Complete Problems and Approximate Solutions

by Sartaj Sahni and Teofilo Gonzalez

Computer, Informs,tion, and -Control : Sciences Institute of Technology University of P~ nnesota t'nneapolis, Minnesota 55455

?deport 74-S T?arch, 1974 This research was supported by University of Z1innesota Research Grant 481-0906-4125-02. Cover design courtesy of Ruth and Jay Leavitt P-Complete Problems and Approximate Solutions by Sartaj Sahni and Teofilo Gonzalex University of Minnesota

Abstract

We study the class of P-Complete problems and show the folloc~7ings i) for any constant s > 0 there is a P-complete problem for which an s-approximate solution can be found in linear time ii) there exist P-Complete problems far which linear time approximate solutions that get closer and closer to the optimal (with increasing problem size) can he found iii) there exist P-Complete problems for which the approximation problems are also P-Complete.

Key Words: P-Complete, approximation, algorithm, polynomial complexity, Iz-Partition, I:- TZaxCut This research was supported by University of r?3nnesota Research Grant 1/481-006- 4125-02.

1. Introduction

Our notion of P-complete corresponds to the one used in [6]. This can easily be seen to be equivalent to that of Cook [2]. A Problem, T. , gill be said to be P-complete iff the following holds: L can. be solved in polynomial determin-istic time iff the class of nondeterministic polynomial time

(Equation Omitted)

is the same as deterministic polynomial time languages; (i.e.

(Equation Omitted)

) hnnth [5] suggests the terminology NP-Complete. However, his notion of "completeness" is that of ICarp [4]. Since the equivalence or nonequivalence of the two notions is not hnornx, we will use the term .iJP-ComnlEae for problems . that can be shown complete with Karn's definition and P-Compleae for those which require the definition a jb ] . The reader- unfamiliar t~r1.th P-Complete problems is referred to j4] and j6 ] . All problems that are '?1P-Complete (i.e. complete under Karp's definitions) are also P-Complete j2 and 6] : The reverse is uel-.noT-m~ Since it appears that P 0 MP, the P-Complete problem probably have no polynomial solution. Puny of these problems, especially the optimisation problems, are of practical significance. Often, as in the case of the Knapsack, problem j7], approximate solutions .(i.a. feasible solutions that are guaranteed to be F reasonalily':'.nlose to the optima.) would be , acceptable so long as they can be obtained cluic%ly (e.g., by an 4(n") algorithm for small I: ) . Johnson j3]

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 9

P-Complete Problems and Approximate Solutions

and Sa'rxxxi j7] have studied some P-Complete problems, vrith respect to obtaining good (i.e. polynomial) approximate algorithms. (For our purposes, an algorithm for a maximization problem t;r:Cll be said to be:

(Equation Omitted)

is the,maximum,val...