We show that" a little more time gives a lot more power to sampling algorithms." We prove
that for every constant k≥ 2, every polynomial time bound t, and every polynomially small ε …

具有常数高度的电路族可能是唯一一类我们能有信心地说我们完全理解的电路族. 在NC0
中的电路族有简单的刻画, 也很容易看出包含关系NC0⊆ AC0 是严格的, 见练习 …

In this paper, we give an oracle under which BPP is equal to probabilistic linear time, an
unusual collapse of a complexity time hierarchy. In addition, we also give oracles where ΔP2 …

The original definition of interactive proof-systems, as given by Goldwasser, Micali and
Rackoff, does not impose limits on the prover's computing power [GMR89]. This is also the …

Let SAT_<(N) denote the following problem. Instance. A conjunction φ of (in) equalities
t_1=t_2 or t_1<t_2, where t_1, t_2 are terms of the form f_1f_2⋯f_s(e), where e∈N, s\geqq0 …

We study the existence of time hierarchies for heuristic algorithms. We prove that a time
hierarchy exists for heuristic algorithms in such syntactic classes as NP and co-NP, and also …

The complexity theoretic concept of levelability is introduced to the accepting density
hierarchy in NP. A set A in NP is levelable with respect to density u (n) if for every polynomial …

In this paper, we extend the techniques used in our previous work to show that there exists a
probabilistic Turing machine running within time $ O (n^ k) $ for all $ k\in\mathbb {N} _1 …

The overarching theme of the following pages is that mathematical logic--centered around
the incompleteness theorems--is first and foremost an investigation of $\textit {computation} …

It is shown by simulation that every language accepted within time n^d by a nondeter-
ministic one-dimensional Turing machine is accepted in linear time by a nondeterministic d …