Browse Prior Art Database

Promise Problems Complete for Complexity Classes

IP.com Disclosure Number: IPCOM000128017D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 8 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

Alan L. Selman: AUTHOR [+3]

Abstract

A general framework is given to obtain hardness results for promise problems that derive from self-reducible decision problems. This general theorem includes as special cases NP-hardness of the Satisfiability promise problem [ESY841 and graph isomorphism hardness of a problem raised by Kirpatrick and subsequently solved by Luks (Luk851-The advantage of our method is that essentially no graph theory is used. Examination of the satisfiability promise.problem shows that if NP n co-NP has a complete language, then a special case of the satisfiabilty promise problem is hard for the class NP n co-NP. As corollaries, if NP n co-NP has a complete language, then strong separability properties exist for NP n co-NP and special cases of the satisfiability decision problem are complete problems for NP n co-NP. All languages considered are over the finite alphabet E 0, 1). When we say that * word x is a formula of logic or a graph, we intend that x is the encoding of either * formula or a graph. The reader is referred to (ESY841 for basic facts and notation about promise problems. I

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

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Promise Problems Complete for Complexity Classes

by Alan L. Selman

TR #85-33

December 1985

Promise Problems Complete for Complexity Classes

Alan L. Selman Computer Science Department Iowa State University Ames, Iowa 50011

December 1985

*This research was supported in part by the National Science Foundation under grant DCR84- 02033.

1 Introduction

A general framework is given to obtain hardness results for promise problems that derive from self-reducible decision problems. This general theorem includes as special cases NP-hardness of the Satisfiability promise problem [ESY841 and graph isomorphism hardness of a problem raised by Kirpatrick and subsequently solved by Luks (Luk851-The advantage of our method is that essentially no graph theory is used. Examination of the satisfiability promise.problem shows that if NP n co-NP has a complete language, then a special case of the satisfiabilty promise problem is hard for the class NP n co-NP. As corollaries, if NP n co-NP has a complete language, then strong separability properties exist for NP n co-NP and special cases of the satisfiability decision problem are complete problems for NP n co-NP. All languages considered are over the finite alphabet E 0, 1). When we say that

* word x is a formula of logic or a graph, we intend that x is the encoding of either

* formula or a graph. The reader is referred to (ESY841 for basic facts and notation about promise problems.

I

2 Self- reducibility

Self-reducibility notions have appeared in the literature in a variety of guises, but the most useful definition is due to Meyer and Paterson [MP79). Their definition follows.

Definition I A partial order

(Equation Omitted)

Iowa State University Page 1 Dec 31, 1985

Page 2 of 8

Promise Problems Complete for Complexity Classes

OK if and only if

(1) every strictly decreasing chain is finite, and there is a polynomial p such that every finite <- decreasing chain is shorter than p of the length ofits maximum element, and

x < y implies

(Equation Omitted)

for some polynomial q, and all x and y in E*.

Definition 2 A set x is self-reducible if and only if there is an OK partial order and a query machine M such that M accepts A in polynomial time with oracle A and, moreover, on any input x in E*, M asks its oracle only about words strictly less than x in the partial order.

Our concern is with sets that are d-self-reducible. This means that on every input word x, the query machine M either

(1) decides membership of x in A in polynomial time without queries to the oracle, or

(H) computes a set of queries

(Equation Omitted)

in polynomial time so that

(Equation Omitted)

All of the known NP-complete problems are d-self-reducible, and Meyer and Pater-son IMP79) and Schnorr ISch76] demonstrate d-self-reducibility of several problems in NP that are not known to be either in P or NP-complete. For every set A C- NP there is a polynomial time recognizable relat...