Author name cluster

R. Beigel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 1995 Journal Article

Approximable Sets

R. Beigel
M. Kummer
F. Stephan

Much structural work on NP-complete sets has exploited SAT′s d-self-reducibility. In this paper, we exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets are p-superterse unless P = NP. In fact, every set that is NP-hard under polynomial-time n o(1)-tt reductions is p-superterse unless P = NP. In particular, no p-selective set is NP-hard under polynomial-time n o(1)-tt reductions unless P = NP. In addition, no easily countable set is NP-hard under Turing reductions unless P = NP. Self-reducibility does not seem to suffice far our main result: in a relativized world, we construct a d-self-reducible set in NP − P that is polynomial-time 2-tt reducible to a p-selective set.

Details DOI

I&C Journal 1995 Journal Article

Quantifying the Amount of Verboseness

R. Beigel
M. Kummer
F. Stephan

We study the fine structure of the classification of sets of natural numbers A according to the number of queries which are needed to compute the n-fold characteristic function of A. A complete characterization is obtained, relating the question to finite combinatorics. In order to obtain an explicit description we consider several interesting combinatorial problems.

Details DOI

I&C Journal 1993 Journal Article

Terse, Superterse, and Verbose Sets

R. Beigel
W.I. Gasarch
J. Gill
J.C. Owings

Let A be a subset of the natural numbers, and let F A n (x 1, .. ., x n ) = 〈χ A (x 1), .. ., χ A (x n )〉, where χ A is the characteristic function of A. An oracle Turing machine with oracle A could certainly compute F A n with n queries to A. There are some sets A (e. g. . the halting set) for which F A n can be computed with substantially fewer than n queries. One key reason for this is that the questions asked to the oracle can depend on previous answers; i. e. , the questions are adaptive. We examine when it is possible to save queries. A set A is terse if the computation of F A n from A requires n queries. A set A is superterse if the computation of FA n from any set requires n queries. A set A is verbose if FA 2 n −1 can be computed with n queries to A. The range of possible query savings is limited by the following theorem: FA n cannot be computed with only ⌊ log n ⌋ queries to a set X unless A is recursive. In addition we produce the following: (1) a verbose set in each truth-table degree and a superterse set in each nonzero truth-table degree; and (2) an r. e. verbose set in each r. e. truth-table degree and an r. e. terse set in each nonzero r. e. Turing degree.

Details DOI