JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Hemachandra, Lane A."
Now showing items 110 of 10

The Boolean Hierarchy: Hardware over NP
Cai, Jinyi; Hemachandra, Lane A. (Cornell University, 198512)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?
Hemachandra, Lane A. (Cornell University, 198612)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
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198604)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
Hemachandra, Lane A. (Cornell University, 198706)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
Cai, Jinyi; Hemachandra, Lane A. (Cornell University, 198606)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 NearTestability: $P^{A} \neq NT^{A}$ With Probability 1
Hemachandra, Lane A. (Cornell University, 198707)The class of neartestable 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
Hemachandra, Lane A. (Cornell University, 198612)This paper structurally characterizes the complexity of ranking. A set is Prankable 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
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198510)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 ... 
OneWay Functions, Robustness, and the NonIsomorphism of NPComplete Sets
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198601)This paper 1. gives a relativized counterexample to the conjectured connection between the existence of oneway functions and the existence of nonisomorphic NPcomplete sets. 2. establishes that in relativized worlds ... 
The Sky is Falling: The Strong Exponential Hierarchy Collapses
Hemachandra, Lane A. (Cornell University, 198608)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 ...