| dc.contributor.author | Askeland, Andreas Reppesgård | |
| dc.date.accessioned | 2016-02-08T23:00:31Z | |
| dc.date.available | 2016-02-08T23:00:31Z | |
| dc.date.issued | 2015 | |
| dc.identifier.citation | Askeland, Andreas Reppesgård. Investigations in complexity theory related to the space hierarchy theorem. Master thesis, University of Oslo, 2015 | |
| dc.identifier.uri | http://hdl.handle.net/10852/49049 | |
| dc.description.abstract | This master thesis investigate space complexity theory, with the motivation of developing a degree theory. A direct application of our investigation is a strengthening of the space hierarchy theorem as stated by Sipser (Sipser, 2006). At the end, we define a degree theory and show some elementary properties of the degree structure. We also present detailed proofs of known results, including a detailed description of a universal Turing machine. | eng |
| dc.language.iso | eng | |
| dc.subject | Complexity | |
| dc.subject | theory | |
| dc.subject | degree | |
| dc.subject | theory | |
| dc.subject | Space | |
| dc.subject | Hierarchy | |
| dc.subject | theorem | |
| dc.subject | universal | |
| dc.subject | Turing | |
| dc.subject | machine | |
| dc.title | Investigations in complexity theory related to the space hierarchy theorem | eng |
| dc.type | Master thesis | |
| dc.date.updated | 2016-02-08T23:00:31Z | |
| dc.creator.author | Askeland, Andreas Reppesgård | |
| dc.identifier.urn | URN:NBN:no-52834 | |
| dc.type.document | Masteroppgave | |
| dc.identifier.fulltext | Fulltext https://www.duo.uio.no/bitstream/handle/10852/49049/1/masterAndrra.pdf | |