April 13th Class Notes - University of Central Florida

April 13th Class Notes Hw# 5 will be worth 50 points and it will be posted tonight or tomorrow Definition of the Class NP 1)Language that can be accepted on a nondeterministic TM in polynomial time. If it isnt in the language it may not

reject in polynomial time 2)Given a certificate, one can verify in polynomial time whether or not an input is in the language Hampath={|G has a Hamiltonian path} This doesnt have a Hampath since there are

three vertices of degree one and we would need a way in and a way out The graph below has a hampath One Hampath for the diagram is

A-B-D-F-E-C This path can be used to represent a certificate. Verifying this path would take less than polynomial time We can also prove that this can NP by checking all path options at once

Hampath={|Gdoesnt have a hamiltonion path There is not an easy certificate that can be generated to prove that no path exists This is Co-NP (compliment NP) Composites ={n|n exists Z+ and there exists a p and q such

that n=p*q} Can easily produce a certificate ie if n=143 p=11 and q=13 Primes={n|there is no way to represent n=p*q, where pa nd q exist in Z+ and P>1 and q>1}

This has been shown to be O(n**6) by AKS Clique={G,K|Graph G has a Clique of size k} The time to determine this would be n choose k A certificate would be all of the nodes in the clique

Subset-sum={(s,target| some subset in s adds up to the target) Brute force method: chack all subsets of S This would take 2**n where |s|=n A certificate could be generated which would include the

subet that adds to the target Example S={7,15,35,19,135,2} target =59 Certificate =7,15,35,2 It is not known if P is a subset of NP or they are equal

Section 7.4 SAT (satisfiability problem) Boolean formula (X1 V X2 V X3) ^(X3V X4) Cook Levin theorem SAT exists in P iff P=NP

Polynomial time mapping problem A< pB iff W exists in A iff f(w) exists in B And f is computable in polynomial time If a polynomial solution to B was known and A< pB, Than there exists a polynomial solution to A To solve A A(w){ 1. 2.

Calculate f(w) Run the solution for B with input f(w) Given a solution to B we solve A by callin the soln to B a polynomial number of times

Partition < p subset sum S= {3,16,19,25,14,201} F(w)=S= {3,16,19,25,14,201} Target = (3+16+19+25+14+201)/2

All problems in NP are poly time reducible to SAT X as NP-Complete and Y has to be in the NP.

Also SAT is NP-Complete To prove a problem is NP_Complete reduce it from a known NP-Complete problem Any prob

Recently Viewed Presentations

  • Tegevusuuring hariduses

    Tegevusuuring hariduses

    (design research, design-based research, design study, design experiment) Mõisted rakendust loova uuringu taustaks Design means "to invent and bring into being" [Webster's Dictionary and Thesaurus, 1992]. Thus, design deals with creating something new that does not exist in nature.
  • Bed, Hart Room, Bed, before 1674 (reproduction)

    Bed, Hart Room, Bed, before 1674 (reproduction)

    Hart Room, Ipswich, MA, reproduced in Metropolitan Museum Bed, Hart Room, Bed, before 1674 (reproduction) Cupboard, Hart Room, made in Plymouth County, MA, 1670-1700 Cradle, Hart Room, made in Eastern Mass, 1640-1680 Charger, Hart Room, made in England, c. 1680...
  • Factors Affecting Tourism - Weebly

    Factors Affecting Tourism - Weebly

    In addition to travel motivators and barriers, there are several other factors that have a direct impact on the tourism industry Just as the cost of travel can act as a barrier, economic prosperity can encourage people to take trips,...
  • OC 2/e Ch 15

    OC 2/e Ch 15

    William H. Brown & Christopher S. Foote ... a new carbon-carbon bond is formed in the process We study addition of these carbon nucleophiles Grignard Reagents Given the difference in electronegativity between carbon and magnesium (2.5 - 1.3), the C-Mg...
  • Stochastic Planning with Concurrent, Durative Actions

    Stochastic Planning with Concurrent, Durative Actions

    Use heuristic search (and reachability information) LAO*, RTDP Use execution and/or Simulation "Actual Execution" Reinforcement learning (Main motivation for RL is to "learn" the model) "Simulation" -simulate the given model to sample possible futures Policy rollout, hindsight optimization etc. Use...
  • Shape of Caring Sue Hatton Senior Nursing Policy

    Shape of Caring Sue Hatton Senior Nursing Policy

    into CYP nursing through foundation degrees, Assistant Practitioner roles and other routes . Next Steps . ... Around 90% of the core principles of education could be agreed by the development of some concenscious . statements from the group, which...
  • DEA ePCS - Duke University

    DEA ePCS - Duke University

    CPRS system must authenticate the Prescriber's credentials on a hard token (Smart Card or PIV Card) CPRS must display a mandatory message with DEA-required intent language that the Prescriber must consent to. Only after the Prescriber consents to the DEA-required...
  • Chapter 16 Covalent Bonding - Chemistry is Fun

    Chapter 16 Covalent Bonding - Chemistry is Fun

    Section 8.2 The Nature of Covalent Bonding OBJECTIVES: Distinguish between a covalent bond and a coordinate covalent bond, and describe how the strength of a covalent bond is related to its bond dissociation energy. Section 8.2 The Nature of Covalent...