Revision as of 05:42, 18 December 2007 edit Doradus (talk \| contribs) Extended confirmed users, Pending changes reviewers 6,033 edits →What machine model?: new section ← Previous edit		Revision as of 20:20, 18 December 2007 edit undo Dcoetzee (talk \| contribs) 37,529 edits →What machine model? Next edit →
Line 148: What kind of machine is used to measure the number of steps or amount of memory required to solve a problem? A [[Random access stored program machine\|RASP machine]]? I don't think it's a [[Turing machine]]. --[[User:P3d0\|P3d0]] ([[User talk:P3d0\|talk]]) 05:42, 18 December 2007 (UTC) :The definitions of major classes are explicitly designed to be robust against "reasonable" changes in the definition of the underlying abstract machine. In typical presentations various types of Turing machines are used but it doesn't matter - RAM models, cache-oblivious models, pretty much everything works fine. That's why we discuss P and not, say, DTIME(n<sup>3</sup>). [[User:Dcoetzee\|Dcoetzee]] 20:20, 18 December 2007 (UTC)

Talk:Computational complexity theory: Difference between revisions