Browse Prior Art Database

Some Subexponentially Recognizable NP-Complete Languages

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

Publishing Venue

Software Patent Institute

Related People

Sartaj K. Sahni: AUTHOR [+3]

Abstract

We look at some NP-Complete languages and show that they can be recognised in ;

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

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Some Subexponentially Recognizable NP-Complete Languages*

by Sartaj K. Sahni

04001 Computer, Information, and Control Sciences Department Institute of Technology University of Minnesota MinneapolisMinneapolis, Minnesota' 55455 R Technical Report July, 1974 *This research was supported by University of Minnesota Research Grant ,#481-0906- 4125-02. Cover design courtesy of :Ruth and Jay Leavitt Some..$ubexponentially Recognizable NP-Complete Languages*

Sartaj: Salmi Department of Computer Science University of Minnesota

Abstract

We look at some NP-Complete languages and show that they can be recognised in ;

1. Introduction

Since the discovery ty Cook [2], of the relationship between the deterministic complexity of languages recognizable in nondeterministic polymonial time (NP) and the complexity of the tautology problem, a lot of attention has been focussed on the problem of finding other problems similarly related to the class r3I'. [1,3,7,8 and 10]. This class of problems has come to be known as the class of NP-Complete problems. The problems in the~.class NP-Complete are stated as language recognition problems and informally, they satisfy the property that each of them is polynomial time recognizable iff all languages in UP are recognizable in deterministic polynomial time (ie P=NP). Thus the class NP-Complete is an equivalence class. At present all known algorithms for these problems are exponential. [1,5,6 and 9] study the problem of finding efficient (polynomial time) approximation algorithms for NP-Complete problems. Some authors have attempted to obtain ~simhexponent3.a1 bane algorithms to obtain the'exqct solution to certain VP-Complete problems.. Thus, Tartan [11].presents an 0(1.286n) for determining the largest cliques in a graph (n is the.number of vertices in the graph) and Horowitz and Sahni [4] present an 0(2r/2) for the sum of subsets and other related problems. However, all these algorithms are still essentially exponential. While in [10] it was remarked that there existed NP- Complete languages that could be recognized in subexponential time (t& of the form 0(2~), where n is the length of the input), we were unable to show this for any "natural" NP-Complete language. In this paper we show that some of the NP-Complete languages studied.'. by Karp [7] and Sahni [8] are recognizable in ,subexponeatial time. The specific problems wee look at area

(i) Sum of subsets [7] (ii) 0-1 Knapsack [8] (iii) Sequencing with deadlines [7] (iv) Clique (7]

In section 2 we briefly review our terminology and then in section 3 we present our results. The reader unfamiliar with the class of UP-Complete languages should see [7] or [8] for a more formal introduction to the subject.

3 2. Terminology and NP-Complete Lanage^,s-

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 8

Some Subexponentially Recognizable NP-Complete Languages

Our terminology corresponds to that of K...