In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size."
I think that this may be missing a constraint. For example, this would imply that finding a Hamiltonian cycle is in NC:
If I give all of the permutations of the vertices of a graph as input, then I can assign a processor to each permutation, and each processor can then check for the appropriate edges in O(|E|) time, which would mean that finding a Hamiltonian cycle would be in NC.
So is there some constraint that is missing from the definition we are using in class, or am I missing something else?
For clarification: Consider a classical TM, which accepts as input a sane representation of a graph, followed by all of the permutations of a graph's vertices. It then performs the best currently known algorithm for finding Hamiltonian Cycles, and as output writes out a permutation of the vertices describing such a cycle.
The algorithm would perform in time linear in the input size, but in time factorial in the order of the input graph. (The extra inputs don't seem to count as computations for a classic TM.)
In the PRAM model (as I have described it), the algorithm would perform in time linear in both the input size, and in the order of the graph. (The extra inputs seem to count as computations for the PRAM model... Which makes me think that "computation" means something subtly different here...)
If this is the way it is supposed to work: awesome. If not, than am I missing some constraints on what the allowed inputs are?