ppt/presentation.xml
ppt/slideMasters/slideMaster1.xml
ppt/slides/slide1.xml
ppt/slides/slide2.xml
ppt/slides/slide3.xml
ppt/slides/slide4.xml
ppt/slides/slide5.xml
ppt/slides/slide6.xml
ppt/slides/slide7.xml
ppt/slides/slide8.xml
ppt/slides/slide9.xml
ppt/notesMasters/notesMaster1.xml
ppt/commentAuthors.xml
ppt/presProps.xml
ppt/viewProps.xml
ppt/theme/theme1.xml
ppt/tableStyles.xml
ppt/slideLayouts/slideLayout1.xml
ppt/slideLayouts/slideLayout2.xml
ppt/media/image1.png
ppt/media/image2.png
ppt/theme/theme2.xml
ppt/notesSlides/notesSlide1.xml
ppt/media/audio1.wav
ppt/media/audio2.wav
ppt/media/image3.jpg
ppt/media/image4.jpg
ppt/media/image5.png
ppt/media/image6.webp
ppt/media/image7.png
ppt/media/image8.jpg
ppt/media/image9.jpg
ppt/notesSlides/notesSlide2.xml
ppt/notesSlides/notesSlide3.xml
ppt/media/image10.jpeg
ppt/media/image11.emf
ppt/media/image12.jpeg
ppt/notesSlides/notesSlide4.xml
ppt/notesSlides/notesSlide5.xml
ppt/notesSlides/notesSlide6.xml
ppt/media/image13.jpeg
ppt/notesSlides/notesSlide7.xml
ppt/notesSlides/notesSlide8.xml
ppt/notesSlides/notesSlide9.xml
ppt/media/audio3.wav
ppt/media/audio4.wav
ppt/media/image14.png
ppt/media/image15.jpeg
ppt/changesInfos/changesInfo1.xml
docProps/core.xml
docProps/app.xml
ppt/media/image26.png
_rels/.rels
ppt/_rels/presentation.xml.rels
ppt/slideMasters/_rels/slideMaster1.xml.rels
ppt/slides/_rels/slide1.xml.rels
ppt/slides/_rels/slide2.xml.rels
ppt/slides/_rels/slide3.xml.rels
ppt/slides/_rels/slide4.xml.rels
ppt/slides/_rels/slide5.xml.rels
ppt/slides/_rels/slide6.xml.rels
ppt/slides/_rels/slide7.xml.rels
ppt/slides/_rels/slide8.xml.rels
ppt/slides/_rels/slide9.xml.rels
ppt/notesMasters/_rels/notesMaster1.xml.rels
ppt/slideLayouts/_rels/slideLayout1.xml.rels
ppt/slideLayouts/_rels/slideLayout2.xml.rels
ppt/notesSlides/_rels/notesSlide1.xml.rels
ppt/notesSlides/_rels/notesSlide2.xml.rels
ppt/notesSlides/_rels/notesSlide3.xml.rels
ppt/notesSlides/_rels/notesSlide4.xml.rels
ppt/notesSlides/_rels/notesSlide5.xml.rels
ppt/notesSlides/_rels/notesSlide6.xml.rels
ppt/notesSlides/_rels/notesSlide7.xml.rels
ppt/notesSlides/_rels/notesSlide8.xml.rels
ppt/notesSlides/_rels/notesSlide9.xml.rels
[Content_Types].xml
Click to edit the title text format Click to edit the outline text format Second Outline Level Third Outline Level Fourth Outline Level Fifth Outline Level Sixth Outline Level Seventh Outline Level Eighth Outline Level Ninth Outline Level <
COSC1107 Computing Theory Analysing complexity Week 10 part 1 Week 10.1 Computing Theory james. .au * With thanks to Intro music ‘Far Over’ playing now … style.visibility ppt_x ppt_y ppt_x ppt_y style.visibility
Computational limits Week 10.1 Computing Theory There are various limits on computation Technological Any computing device has a finite memory, storage capacity, processing speed, bandwidth, … There is always a problem “just beyond” any technology Example: Platypus tournament Practical (Complete) Algorithmic solutions exist Complexity is too high for problems beyond a smallish size Example: Hamiltonian circuit problem Fundamental No (complete) algorithmic solutions exist Will always be beyond any technology Example: Halting problem style.visibility ppt_w ppt_h style.rotation
Problems Week 10.1 Computing Theory Problems in P: sorting, linear programming, primality testing , matrix inversion, greatest common divisor, … Problems in NP: Travelling salesman, Hamiltonian circuit , vertex cover, 3-satisfiability , graph colouring, subgraph isomorphism, clique problem, knapsack problem, bin packing, serializability, normal form violation, job scheduling, timetabling, integer programming, mastermind, minesweeper, Petri net reachability, presentation of finite groups, + thousands more … tractable intractable factorisation style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Complexity Computing Theory Week 10.1 LOGTIME NP EXPSPACE Turing machines P PSPACE EXPTIME ?? ?? Our main focus
Complexity Computing Theory Week 10.1 NP P Finding a solution is easy Checking a solution is easy; Finding a solution is hard. Checking a solution is hard style.visibility style.visibility style.visibility
Complexity Computing Theory Week 10.1 NP P Finding a solution is easy Checking a solution is easy; Finding a solution is hard. 3SAT HC TSP Primality, sorting, … … “Nobody is certain that P and NP are different, but many experts believe so …” style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility ppt_x ppt_y style.visibility ppt_x ppt_y
P = NP? Computing Theory Week 10.1 Clearly P ⊆ NP. Is NP ⊆ P? No proof either way! Clay Institute in USA will give US$1 million to anyone who can settle this question! Same prize for 6 other problems First offered in 2000, only one has been claimed See http://www.claymath.org/millennium-problems and http://www.claymath.org/millennium-problems/p-vs-np-problem How could you prove P = NP? Find a polynomial-time algorithm on a (deterministic) TM for an NP-complete problem How could you prove P ≠ NP? Reason about all possible algorithms? (!!) Neither has been done so far …
P = NP? Computing Theory Week 10.1 Many sub-classes of NP and PSPACE No need to know all of these! All could be empty if P = NP style.visibility style.visibility style.visibility ppt_x ppt_y
That’s it! Week 5 Computing Theory I am out of here! The lecture just halted. style.visibility ppt_y style.visibility ppt_y ppt_w ppt_h ppt_x ppt_y style.visibility ppt_w ppt_h ppt_x ppt_y style.visibility style.visibility ppt_w ppt_h ppt_x ppt_y ppt_w ppt_h style.rotation style.visibility style.visibility ppt_x ppt_y
‹#›
Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level <
Click to edit Master title style <
1 This cover slide full of examples of structures. Colour field to the right is discretised into cells we can identify by row and column. Need precision and agreed conventions to speak about cells in our algorithms and for making sense of the data values – here colour values held by cells. For example is cell indexed by 12 (x-axis) and 11 (y-axis) a blue colour value or not? Test it! Discrete Structures are not ‘Being’ but ‘Doing’. Well: are we starting to count from 0, or 1? Are we counting from the left top or left bottom or any other way? Look at the graph to the left. Graphs are central to many algorithms and models. And this course will get to graphs in more detail. Let’s say this is a model of evidence collected in a investigation. Vertices might represent persons of interest, edges strong evidence of communication between them in the last couple of months. A key investigative question might be, “has the person of interest communicated with the victim?” According to the evidence? Test it! P top left, V bottom right, say. How do we prove this claim?
2
3
4
5
6
7
8
9
PowerPoint Presentation 990 2018-02-27T21:31:56Z 2021-08-05T09:06:55Z
20355 718 Microsoft Office PowerPoint On-screen Show (4:3) 117 9 9 0 0 false Fonts Used 5 Theme 1 Slide Titles 9 Comic Sans MS StarSymbol Times Wingdings 1_Default Design COSC1107 Computing Theory Analysing complexity Week 10 part 1 Computational limits Problems Complexity Complexity Complexity P = NP? P = NP? That’s it! false false false 16.0000