Now showing items 1-6 of 6

• #### Computational Complexity and the Existence of Complexity Gaps ﻿

(Cornell University, 1969-08)
Computational Complexity and the Existence of Complexity Gaps
• #### Fast Parallel Matrix and GCD Computations ﻿

(Cornell University, 1982-04)
We present parallel algorithms to compute the determinant and characteristic polynomial of n x n-matrices and the gcd of polynomials of degree $\leq$n. The algorithms use parallel time $O(\log^{2}n)$ and a polynomial ...
• #### Merging on Parallel Models of Computation ﻿

(Cornell University, 1981-09)
A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models, we show that \$\log ...
• #### On the Efficiency of Programs in Subrecursive Formalisms ﻿

(Cornell University, 1970-03)
NO ABSTRACT SUPPLIED
• #### Routing in Networks ﻿

(Cornell University, 1981-11)
NO ABSTRACT SUPPLIED
• #### Some Comments on Functional Self-Reducibility and the NP Hierarchy ﻿

(Cornell University, 1976-07)
In Valiant [11] and Schnorr [9], concepts of "functional self-reducibility" are introduced and investigated. We concentrate on the class NP and on the NP hierarchy of Meyer and Stockmeyer [7] to further investigate these ...