Now showing items 1-10 of 10

• #### The Boolean Hierarchy: Hardware over NP ﻿

(Cornell University, 1985-12)
In this paper, we study the complexity of sets formed by boolean operations \$(\bigcup, \bigcap,\$ and complementation) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together ...
• #### Can P and NP Manufacture Randomness? ﻿

(Cornell University, 1986-12)
This paper studies how Kolmogorov complexity dictates the structure of standard deterministic and nondeterministic classes. We completely characterize, in Kolmogorov terms, when \$P^{NP[\log]}= P^{NP}\$, where [log] ...
• #### Complexity Classes Without Machines: On Complete Languages for UP ﻿

(Cornell University, 1986-04)
This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. ...
• #### Counting in Structural Complexity Theory ﻿

(Cornell University, 1987-06)
Structural complexity theory is the study of the form and meaning of computational complexity classes. Complexity classes - P, NP, Probabilistic P, PSPACE, etc. - are formalizations of computational powers - deterministic, ...
• #### Exact Counting is as Easy as Approximate Counting ﻿

(Cornell University, 1986-06)
We show that exact counting and approximate counting are polynomially equivalent. That is \$P^{#P} = P^{Approx#P}\$, where #\$P\$ is a function that computes the number of solutions to a given Boolean formula \$f\$ (denoted ...
• #### On Parity and Near-Testability: \$P^{A} \neq NT^{A}\$ With Probability 1 ﻿

(Cornell University, 1987-07)
The class of near-testable sets, NT, was defined by Goldsmith, Joseph, and Young. They noted that \$P \subseteq NT \subseteq PSPACE\$, and asked whether P=NT. This note shows that NT shares the same \$m\$-degree as the ...
• #### On Ranking ﻿

(Cornell University, 1986-12)
This paper structurally characterizes the complexity of ranking. A set is P-rankable if there is a polynomial time computable function \$f\$ so that for all \$x, f(x)\$ computes the number of elements of \$A\$ that are ...
• #### On Sparse Oracles Separating Feasible Complexity Classes ﻿

(Cornell University, 1985-10)
This note clarifies which oracles separate NP from P and which do not. In essence, we are changing our research paradigm from the study of which problems can be relativized in two conflicting ways to the study and ...
• #### One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets ﻿

(Cornell University, 1986-01)
This paper 1. gives a relativized counterexample to the conjectured connection between the existence of one-way functions and the existence of non-isomorphic NP-complete sets. 2. establishes that in relativized worlds ...
• #### The Sky is Falling: The Strong Exponential Hierarchy Collapses ﻿

(Cornell University, 1986-08)
This paper investigates the complexity of the high levels of the exponential hierarchy [HY84,HIS85]: Are they hard, and if so why are they hard? We show that \$P^{NE} = NP^{NE}\$. From this we conclude that the strong ...