@InProceedings{   Schonhage:ICALP:1979,
  Author        = {Sch{\"o}nhage, Arnold},
  Editor        = "Maurer, Hermann A.",
  Abstract      = "We study the power of deterministic successor RAM's with extra instructions like +,*,⋎ and the associated classes of problems decidable in polynomial time. Our main results are NP ... PTIME (+,*,⋎) and PTIME(+,*) ... RP, where RP denotes the class of problems randomly decidable (by probabilistic TM's) in polynomial time.",
  Address       = "Berlin, Heidelberg",
  BookTitle     = "Automata, Languages and Programming",
  date-added    = "2021-01-21 09:10:02 +0100",
  date-modified = "2023-08-22 11:54:29 +0200",
  ISBN          = "978-3-540-35168-9",
  Pages         = "520--529",
  Publisher     = "Springer Berlin Heidelberg",
  Title         = "On the power of random access machines",
  Year          = "1979",
  bdsk-url-1    = "https://link.springer.com/chapter/10.1007/3-540-09510-1\_42",
  File          = "On the power of random access machines - Schönhage1979\_Chapter\_OnThePowerOfRandomAccessMachin - a - k.pdf"
}

@InProceedings{ Schonhage:ICALP:1979, Author = {Sch{\"o}nhage, Arnold}, Editor = "Maurer, Hermann A.", Abstract = "We study the power of deterministic successor RAM's with extra instructions like +,,⋎ and the associated classes of problems decidable in polynomial time. Our main results are NP ... PTIME (+,,⋎) and PTIME(+,*) ... RP, where RP denotes the class of problems randomly decidable (by probabilistic TM's) in polynomial time.", Address = "Berlin, Heidelberg", BookTitle = "Automata, Languages and Programming", date-added = "2021-01-21 09:10:02 +0100", date-modified = "2023-08-22 11:54:29 +0200", ISBN = "978-3-540-35168-9", Pages = "520--529", Publisher = "Springer Berlin Heidelberg", Title = "On the power of random access machines", Year = "1979", bdsk-url-1 = "https://link.springer.com/chapter/10.1007/3-540-09510-1_42", File = "On the power of random access machines - Schönhage1979_Chapter_OnThePowerOfRandomAccessMachin - a - k.pdf" }