4 ms·

r/confidentlyincorrect complexity is wrt a particular model of computation - a turing machine. turing machines are sequential (NTMs aren't). run time on a para

r/confidentlyincorrect complexity is wrt a particular model of computation - a turing machine. turing machines are sequential (NTMs aren't). run time on a parallel model is not necessarily a constant off from run time on a sequential model.

colanderman 6y ago
Snark aside, GP is asking about GPUs. GPUs are not nondeterministic Turing machines.
- anon_tor_12345 6y ago
  like the other comment alludes to it's not constant it's a function of block size and the size of the matrices http://www.ijcee.org/vol9/949-E1621.pdf http://www.ijcee.org/vol9/949-E1621.pdf you edited your comment. it said what's the speed up on GPUs (which i provided). >GPUs are not nondeterministic Turing machines for small problem size that's exactly what they are (or any multicore cpu for that matter) >The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine#Intuition https://en.wikipedia.org/wiki/Nondeterministic_Turing_machin...
  - colanderman 6y ago
    > for small problem size that's exactly what they are O notation does not apply to small problems. It is strictly concerned with asymptotic behavior.
    - anon_tor_12345 6y ago
      you're completely missing the point (again). the point is that complexities (even asymptotic) of sequential algorithms don't apply to parallelizations of those algorithms.
      - aquadrop 6y ago
        Only for infinite number of parallelized processors?
  - tsimionescu 6y ago
    An NTM is one which can run arbitrarily many branches in parallel. So parallel processors are not NTMs, since they can only run a fixed number of branches in parallel. It's true that for small problems they are indistinguishable, but in the context of discussing big O notation that is irrelevant. For the purposes of computing asymptotic time complexity, whether the algorithm is run on a 1 core system or an M core system is usually irrelevant.

colanderman 6y ago

Snark aside, GP is asking about GPUs. GPUs are not nondeterministic Turing machines.

anon_tor_12345 6y ago
like the other comment alludes to it's not constant it's a function of block size and the size of the matrices http://www.ijcee.org/vol9/949-E1621.pdf http://www.ijcee.org/vol9/949-E1621.pdf you edited your comment. it said what's the speed up on GPUs (which i provided). >GPUs are not nondeterministic Turing machines for small problem size that's exactly what they are (or any multicore cpu for that matter) >The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine#Intuition https://en.wikipedia.org/wiki/Nondeterministic_Turing_machin...
- colanderman 6y ago
  > for small problem size that's exactly what they are O notation does not apply to small problems. It is strictly concerned with asymptotic behavior.
  - anon_tor_12345 6y ago
    you're completely missing the point (again). the point is that complexities (even asymptotic) of sequential algorithms don't apply to parallelizations of those algorithms.
    - aquadrop 6y ago
      Only for infinite number of parallelized processors?
- tsimionescu 6y ago
  An NTM is one which can run arbitrarily many branches in parallel. So parallel processors are not NTMs, since they can only run a fixed number of branches in parallel. It's true that for small problems they are indistinguishable, but in the context of discussing big O notation that is irrelevant. For the purposes of computing asymptotic time complexity, whether the algorithm is run on a 1 core system or an M core system is usually irrelevant.