Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Resource-bounded measure:
TR95-028 | 9th June 1995
Eric Allender, Martin Strauss

Measure on P: Robustness of the Notion

In (Allender and Strauss, FOCS '95), we defined a notion of
measure on the complexity class P (in the spirit of the work of (Lutz,
JCSS '92) that provides a notion of measure on complexity classes at least
as large as E, and the work of (Mayordomo, Phd. ... more >>>

TR99-034 | 30th August 1999
Wolfgang Merkle

The global power of additional queries to p-random oracles.

We consider separations of reducibilities in the context of
resource-bounded measure theory. First, we show a result on
polynomial-time bounded reducibilities: for every p-random set R,
there is a set which is reducible to R with k+1 non-adaptive
queries, but is not reducible to any other p-random set with ... more >>>

TR03-040 | 3rd June 2003
Philippe Moser

RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

We use recent results on the hardness of resource-bounded
Kolmogorov random strings, to prove that RP is small in SUBEXP
We also prove that if NP is not small in SUBEXP, then
NP=AM, improving a former result which held for the measure ... more >>>

TR04-047 | 22nd April 2004
Xiaoyang Gu

A note on dimensions of polynomial size circuits

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

TR05-010 | 8th December 2004
Olivier Powell

Almost Completeness in Small Complexity Classes

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

TR05-045 | 12th April 2005
Philippe Moser

Martingale Families and Dimension in P

Revisions: 1

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,
that get rid of some drawbacks of previous measure notions:
martingale families can make money on all strings,
and yield random sequences with an equal frequency of 0's and 1's.
As applications to F-measure,
more >>>

TR06-039 | 28th February 2006
John Hitchcock, A. Pavan

Comparing Reductions to NP-Complete Sets

Under the assumption that NP does not have p-measure 0, we
investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive
reductions: there is a problem that is Turing-complete for NP but
not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

TR09-022 | 16th February 2009
Jack H. Lutz, Elvira Mayordomo

Inseparability and Strong Hypotheses for Disjoint NP Pairs

Revisions: 1

This paper investigates the existence of inseparable disjoint
pairs of NP languages and related strong hypotheses in
computational complexity. Our main theorem says that, if NP does
not have measure 0 in EXP, then there exist disjoint pairs of NP
languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable.
We also relate ... more >>>

TR18-013 | 18th January 2018
John Hitchcock, Adewale Sekoni

Nondeterminisic Sublinear Time Has Measure 0 in P

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

TR18-018 | 22nd January 2018
John Hitchcock, Adewale Sekoni, Hadi Shafei

Polynomial-Time Random Oracles and Separating Complexity Classes

Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random
oracle A, with probability 1. We investigate whether this result
extends to individual polynomial-time random oracles. We consider two
notions of random oracles: p-random oracles in the sense of
martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ... more >>>

ISSN 1433-8092 | Imprint