Now showing items 1-3 of 3

    • 2.25 N-Lower Bound on the Combinational Complexity of Boolean Functions 

      Paul, Wolfgang J. (Cornell University, 1974-12)
      Consider the combinational complexity L(f) of Boolean functions over the basis $\Omega = \{f|f:\{0,1\}^{2} \rightarrow \{0,1\}\}$. A new Method for proving linear lower bounds of size 2n is presented. Combining it with ...
    • On Time Versus Space 

      Hopcroft, John E.; Paul, Wolfgang J.; Valiant, Leslie (Cornell University, 1975-12)
      It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Consequently, for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity ...
    • Realizing Boolean Functions on Disjoint Sets of Variables 

      Paul, Wolfgang J. (Cornell University, 1975-10)
      For switching functions $f$ let $C(f)$ be the combinatorial complexity of $f$. We prove that for every $\varepsilon greater than 0$ there are arbitrarily complex functions $f:\{0,1\}^{n} \rightarrow \{0,1\}^{n}$ such that ...