Browse Prior Art Database

On the 'Accepting Density' Hierarachy in NP

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

Publishing Venue

Software Patent Institute

Related People

Shlomo Moran: AUTHOR [+3]

Abstract

Sets in NP are characterized according to the ratio, called the "accepting density", between accepting and non-accepting computations of elements in the sets, thus generalizing the concept of "random solvability in polynomial time". Some of the results are:

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On the 'Accepting Density' Hierarachy in NP

by Shlomo Moran

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Cover design courtesy of Ruth and Jay Leavitt. Technical Report 79-29 December On the "Accepting Density" Hierarchy in NP by

Shlomo Moran

ABSTRACT

Sets in NP are characterized according to the ratio, called the "accepting density", between accepting and non-accepting computations of elements in the sets, thus generalizing the concept of "random solvability in polynomial time". Some of the results are:

1. There exists, a priori, an infinite hierarchy of classes of sets in NP with the following properties: (a) If A, B E NP and each is polynomially reducible to the other, then A and B belong to the same class in the hierarchy.

(b) As we ascend to higher classes in the hierarchy, the accepting density decreases (the lowest class being P).

2. A number of decision problems concerning this hierarchy, such as "1,lhich classes in the hierarchy are not empty?" and "Which density class includes the NP complete sets?" have different answers under different relativizations. Hence, probably, they cannot be solved by methods known today. On the "Accepting Density" Hierarchy in NP

by Shlomo Moran

Introduction

The class NP of sets which are recognizable by a polynomial .time nondeterministic algorithms is on the focus of-many researchers for a long time, especially since the pioneering works of Cook (4j and Karp ([ 7.J), and some interesting results concerning the structure of this class had been obtained since (e.g. - [8,3]. )

A few years ago it was observed that there are some sets in NP, which though they don't have (yet) a polynomial time deterministic algorithms which solves.them, they can actually bF:solved in polynomial time by probabilistic algorithms [11,9.,2]. This is due to the fact that there are polynomial time nondeterministic algor- ithms solving those problems, which have the following property: If some input is accepted by such an algorithm, then at least 1/2 of the computations of that algorithm on this input are accepting computations. This fact prompted some researchers to characterize sets in NP according to the ratio between the numbers of accepting

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 11

On the 'Accepting Density' Hierarachy in NP

computations and the number of all possible computations for strings in those sets. (See ,e.g.
[1].) We shall refer to that ratio above as the "accepting density " (This notation wassuggested by Adleman in [1)),

In section 1 we give the definitions and the background for the paper. Section 2 deals with an analogue of the "speed up" phenomena. in the time hierarchy - theaphenomena of "density- increasing" in the density hierarchy. In section 3 the invariance of the accepting density under polynomial time reductions is investigated. In section...