eCommons

 

On Some Central Problems in Computational Complexity

dc.contributor.authorSimon, Janosen_US
dc.date.accessioned2007-04-23T17:48:15Z
dc.date.available2007-04-23T17:48:15Z
dc.date.issued1975-01en_US
dc.description.abstractIn this thesis we examine some of the central problems in the theory of computational complexity, like the trade-offs between time and memory, the power of nondeterminism and parallelism, and the speed gained by adding new operations to random access machines. Our main result is the cahracterization of the power of multiplication in random access acceptors: we show, in Chapter 3, that for such models nondeterministic and deterministic computations are polynomially related and that there is a polynomial relationship between the amount of time required for acceptance by random access machines with multiplication, and the amount of tape required by Turing machines. Thus, the additional power gained by using multiplication is the same as that of memory over time (if any). We derive similar results for some other interesting instruction sets. We also have some results for probabilistic and nondeterministic computations: we define threshold machines and show how probabilistic Turing machines may simulate them, and exhibit a set of complete problems for threshold machines. For nondeterministic computations, we present a hierarchy of the elementary recursive languages obtained by polynomially bounded quantification over objects of higher and higher type, which represent nondeterministic time bounded computations with larger and larger bounds. Finally, we discuss some deterministic computations, and conclude with a look at some open problems.en_US
dc.format.extent7057241 bytes
dc.format.extent2732210 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-224en_US
dc.identifier.urihttps://hdl.handle.net/1813/6975
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn Some Central Problems in Computational Complexityen_US
dc.typetechnical reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
75-224.pdf
Size:
6.73 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
75-224.ps
Size:
2.61 MB
Format:
Postscript Files