Show simple item record

dc.contributor.supervisorDomaratzki, Michael (Computer Science)en_US
dc.contributor.authorKolybabi, Mak
dc.date.accessioned2019-09-12T20:23:49Z
dc.date.available2019-09-12T20:23:49Z
dc.date.issued2019-08-13en_US
dc.date.submitted2019-08-13T21:06:25Zen
dc.identifier.urihttp://hdl.handle.net/1993/34243
dc.description.abstractThe Internet core protocols are the networking protocols that the Internet is built on, a subset of which are implemented on every device connected to the Internet. The specifications of these protocols can span dozens of documents, making accurately understanding and implementing them difficult. The Domain Name System is one of the Internet's core protocols, providing a distributed, hierarchical database primarily intended to map between the names and addresses of hosts. Modern DNS contains a plethora of complex and interacting features, defined across a number of documents, evolving over the course of over thirty years. I show that a network of specially-configured hosts implementing a subset of DNS operate as logic gates. I then describe how such gates can communicate to form Boolean circuits. Finally, I discuss CSAT and NP-completeness.en_US
dc.language.isoengen_US
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectNP-completeen_US
dc.subjectComputer scienceen_US
dc.subjectCSATen_US
dc.subjectDNSen_US
dc.titleNetworks of hosts implementing DNS are NP-completeen_US
dc.typeinfo:eu-repo/semantics/masterThesis
dc.typemaster thesisen_US
dc.degree.disciplineComputer Scienceen_US
dc.contributor.examiningcommitteeCameron, Helen (Computer Science)en_US
dc.contributor.examiningcommitteeGraham, Peter (Computer Science)en_US
dc.contributor.examiningcommitteeJeffrey, Ian (Electrical & Computer Engineering)en_US
dc.degree.levelMaster of Science (M.Sc.)en_US
dc.description.noteOctober 2019en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record