Now showing items 1-3 of 3

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

(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 ﻿

(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 ﻿

(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 ...