Premium
Machines Over the Reals and Non‐Uniformity
Author(s) -
Cucker Felipe
Publication year - 1997
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19970430202
Subject(s) - section (typography) , mathematical proof , alphabet , computer science , subject (documents) , state (computer science) , mathematics , theoretical computer science , calculus (dental) , mathematical economics , algorithm , linguistics , medicine , philosophy , geometry , dentistry , operating system , library science
We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet ‐ say {0,1} ‐ which can be decided by real machines working under several resource restrictions. Non‐uniformity appears here in a natural way. However, since this is a technical concept which is not widely known, we summarize in Section 2 some of the intuitive notions, as well as a few basic theorems related to it. In Section 3 we do this for the subject of real machines and then, in Section 4 we present the state of the art of the surveyed topic. We devote Section 1 to introduce the main concepts of complexity theory. Proofs in this article are quite sketchy and are included more to convey intuitive ideas than to completely prove the claimed statements. Bibliographical references to the original literature are supplied for the latter purpose.