Can we solve an EXPTIME-complete problem in polynomial time given 2^N processors?(N is the size of input).

  • 2
    $\begingroup$ "Does a DTM M hold after k steps on input x" is the canonical EXPTIME complete problem. I don't think general TM simulation profits from many processors, so I think the answer to your question is no. $\endgroup$ – adrianN Dec 6 '13 at 10:38
  • 1
    $\begingroup$ in some cases yes, in some cases no, it depend on the internal "coupling" of the problem loosely related to how m,uch communication is reqd between processors. for "embarrassingly parallel" problems the answer is yes. there are some open theoretical questions in this area... efficient parallel algorithms is sometimes called the NC class... $\endgroup$ – vzn Dec 6 '13 at 18:28
  • $\begingroup$ I agree with vzn, it is possible. However, it depends on the complexity of the problem in hand. Not all solutions found using parallel algorithms are work optimal and if they aren't work optimal, its a waste. $\endgroup$ – Polynomial Proton Jan 31 '14 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.