2 replaced http://scicomp.stackexchange.com/ with https://scicomp.stackexchange.com/ edited Apr 13 '17 at 12:53 this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms. in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $$n$$-body problems maybe relatively difficult to efficiently parallelize as the $$n$$ increases because there are $$n^2$$ interactions between all the $$n$$ points. they added 6 others later in the paper and suggest that a last one called "FSMs" (p14) where the problem involves computing FSM like calculations (such as the $$n$$th state of the FSM) may be the opposite of "embarrassingly parallel" something they propose calling "embarrassingly sequential". this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms. in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $$n$$-body problems maybe relatively difficult to efficiently parallelize as the $$n$$ increases because there are $$n^2$$ interactions between all the $$n$$ points. they added 6 others later in the paper and suggest that a last one called "FSMs" (p14) where the problem involves computing FSM like calculations (such as the $$n$$th state of the FSM) may be the opposite of "embarrassingly parallel" something they propose calling "embarrassingly sequential". see also are there famous algorithms in sci. comp. that cant be parallelized, scicomp.se this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms. in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $$n$$-body problems maybe relatively difficult to efficiently parallelize as the $$n$$ increases because there are $$n^2$$ interactions between all the $$n$$ points. they added 6 others later in the paper and suggest that a last one called "FSMs" (p14) where the problem involves computing FSM like calculations (such as the $$n$$th state of the FSM) may be the opposite of "embarrassingly parallel" something they propose calling "embarrassingly sequential". see also are there famous algorithms in sci. comp. that cant be parallelized, scicomp.se 1 answered Jan 12 '14 at 18:17 vzn 9,61811 gold badge1919 silver badges4242 bronze badges this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms. in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $$n$$-body problems maybe relatively difficult to efficiently parallelize as the $$n$$ increases because there are $$n^2$$ interactions between all the $$n$$ points. they added 6 others later in the paper and suggest that a last one called "FSMs" (p14) where the problem involves computing FSM like calculations (such as the $$n$$th state of the FSM) may be the opposite of "embarrassingly parallel" something they propose calling "embarrassingly sequential". see also are there famous algorithms in sci. comp. that cant be parallelized, scicomp.se