Now showing items 1-10 of 10

    • The Boolean Hierarchy: Hardware over NP 

      Cai, Jin-yi; Hemachandra, Lane A. (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? 

      Hemachandra, Lane A. (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 

      Hartmanis, Juris; Hemachandra, Lane A. (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 

      Hemachandra, Lane A. (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 

      Cai, Jin-yi; Hemachandra, Lane A. (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 

      Hemachandra, Lane A. (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 

      Hemachandra, Lane A. (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 

      Hartmanis, Juris; Hemachandra, Lane A. (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 

      Hartmanis, Juris; Hemachandra, Lane A. (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 

      Hemachandra, Lane A. (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 ...