Algorithm Analysis: P and NP

Podcast

Play an AI-generated podcast conversation about this lesson

Download our mobile app to listen on the go

Get App

Questions and Answers

Hvað er átt við með ákvörðunarverkefni í samhengi við reiknirit?

Verkefni þar sem útkoman er rauntala.
Verkefni þar sem útkoman er annaðhvort já eða nei. (correct)
Verkefni þar þarf að finna stysta veg milli tveggja punkta.
Verkefni þar sem útkoman er listi af tölum.

Hvernig er tímaflækja reiknirits oftast mæld?

Með því að mæla meðaltíma yfir mörg keyrslutilfelli.
Með því að mæla versta tilfellis tíma. (correct)
Með því að mæla minnsta mögulega minnisnotkun.
Með því að mæla hraðasta tíma sem reikniritið getur keyrt.

Hvað táknar $T(n)$ í samhengi við reiknirit?

Besti tími sem reikniritið getur keyrt.
Meðaltími sem reikniritið keyrir yfir öll möguleg inntök.
Minnsta mögulega minnisnotkun reikniritsins.
Versti tími sem reikniritið getur keyrt miðað við inntaksstærð $n$. (correct)

Hvað er átt við með 'margliðutíma' í flækjugreiningu reiknirita?

Tíminn sem það tekur reiknirit að leysa verkefni vex í margliðufalli með stærð inntaksins. (B)

Signup and view all the answers

Hvað þýðir það ef verkefni er í flokknum P ('polynomial time')?

Til er reiknirit sem leysir verkefnið í margliðutíma. (A)

Signup and view all the answers

Hver er munurinn á Euler hring og Hamilton hring í grafi?

Euler hringur fer í gegnum allar brúnir nákvæmlega einu sinni, en Hamilton hringur fer í gegnum alla hnúta nákvæmlega einu sinni. (C)

Signup and view all the answers

Hvers vegna er 'brute force' aðferðin ekki talin hagkvæm leið til að finna Hamilton hring í stóru grafi?

Vegna þess að fjöldi mögulegra hringa vex mjög hratt með stærð grafsins. (B)

Signup and view all the answers

Hver er munurinn á því að ákvarða hvort tiltekið graf inniheldur Euler hring á móti Hamilton hring?

Að finna Euler hring er í flokknum P, en að finna Hamilton hring er í flokknum NP. (A)

Signup and view all the answers

Gefin tala $N$, hver er tímaflækjan við að athuga hvort $N$ sé frumtala með því að deila í hana með öllum tölum frá 2 upp í $\sqrt{N}$?

$O(\sqrt{N})$ (C)

Signup and view all the answers

Hvað er átt við með 'stærð inntaks' þegar tala $N$ er gefin sem inntak í reiknirit?

Fjöldi bita sem þarf til að tákna $N$ í tvíundakerfi. (C)

Signup and view all the answers

Hver er áætluð stærð í bitum fyrir tölu $N$?

$\log_2(N)$ (A)

Signup and view all the answers

Ef reiknirit hefur tímaflækju $O(\sqrt{N})$, og stærð inntaks er $n = \log_2(N)$, hver er þá tímaflækjan í tilliti til $n$?

$O(2^{n/2})$ (A)

Signup and view all the answers

Hvað þýðir það að verkefni sé í flokknum NP?

Ef svarið er já, þá er til sönnun sem hægt er að staðfesta í margliðutíma. (B)

Signup and view all the answers

Ef Hamilton-leið er í NP, hvað þýðir það?

Ef tiltekin leið er Hamilton-leið, þá er hægt að staðfesta það í margliðutíma. (B)

Signup and view all the answers

Hvað einkennir co-NP flokkinn?

Ef svarið er nei, þá er til sönnun sem hægt er að staðfesta í margliðutíma. (D)

Signup and view all the answers

Ef tala $N$ er ekki frumtala, hvað felur sönnun þess í sér?

Að finna tvær tölur $a$ og $b$, stærri en 2, þannig að $N = a * b$. (B)

Signup and view all the answers

Hvað er átt við með því að frumtölur séu í bæði NP og co-NP?

Það er bæði auðvelt að sanna að tala sé frumtala og að tala sé ekki frumtala í margliðutíma. (D)

Signup and view all the answers

Hvað felur í sér að öll verkefni í P eru einnig í NP?

Að öll verkefni sem hægt er að leysa í margliðutíma, geta haft sönnun sem hægt er að staðfesta í margliðutíma. (B)

Signup and view all the answers

Ef verkefni A er í P, hvað þýðir það fyrir sönnun á tilviki af A?

Það er engin þörf á sönnun, þar sem hægt er að reikna svarið í margliðutíma. (D)

Signup and view all the answers

Hvað er CircuitSAT verkefnið?

Að finna inntak fyrir gefna rafrás sem gefur útkomuna 1. (A)

Signup and view all the answers

Ef CircuitSAT er í NP, hvað þýðir það?

Ef tiltekin inntaksgildi gefa útkomuna 1, þá er hægt að staðfesta það í margliðutíma. (B)

Signup and view all the answers

Hver er munurinn á P og NP vandamálum?

P vandamál er hægt að leysa í margliðutíma, en fyrir NP vandamál er hægt að sannreyna lausn í margliðutíma ef hún er gefin. (C)

Signup and view all the answers

Hver er skilgreiningin á NP-fullkomnum (NP-complete) vandamálum?

Vandamál sem er bæði í NP og hægt er að umbreyta öllum öðrum NP vandamálum í það í margliðutíma. (B)

Signup and view all the answers

Hvað myndi það þýða ef sýnt væri fram á að P = NP?

Öll vandamál sem hægt er að sannreyna lausn fyrir í margliðutíma, væri einnig hægt að leysa í margliðutíma. (D)

Signup and view all the answers

Hver er helsti munurinn á ákvörðunarvandamáli (decision problem) og hagræðingarvandamáli (optimization problem)?

Ákvörðunarvandamál spyrja já/nei spurningar en hagræðingarvandamál leita að bestu lausn. (A)

Signup and view all the answers

Hvaða fullyrðing er sönn um samband P, NP og NP-fullkominna vandamála?

Öll P vandamál eru í NP. (C)

Signup and view all the answers

Hvað er 'reducible' í samhengi við flækjustig NP vandamála?

Að vandamáli A er hægt að breyta í vandamál B þannig að ef B er leyst, þá er A einnig leyst. (A)

Signup and view all the answers

Hver er munurinn á flækjustiginu $O(n)$ og $O(2^n)$?

$O(2^n)$ vex hraðar með inntaksstærð en $O(n)$. (D)

Signup and view all the answers

Hver af eftirfarandi fullyrðingum er sönn um samband NP og co-NP?

Ef P = NP, þá er NP = co-NP. (C)

Signup and view all the answers

Hvað er átt við með heildsölu reikniriti (heuristic algorithm)?

Reiknirit sem finnur hugsanlega góða lausn, en ekki er víst að hún sé sú besta. (A)

Signup and view all the answers

Af hverju er dulkóðun mikilvæg í nútíma tölvunarfræði?

Til að tryggja að gögn séu ólæsileg fyrir óviðkomandi. (B)

Signup and view all the answers

Hver er helsta áskorunin við að takast á við NP-fullkomin vandamál í raunveruleikanum?

Þau taka of langan tíma að leysa fyrir stór inntök. (A)

Signup and view all the answers

Hvað er átt við með 'approximationsreiknirit' (approximation algorithm)?

Reiknirit sem finnur lausn sem er innan ákveðins vikmarka frá bestu lausn. (D)

Signup and view all the answers

Ef þú ert með NP-fullkomið vandamál, hvaða aðferðir gætir þú notað til að takast á við það?

Leita að approximationsreiknirit eða heildsölu reikniriti. (A)

Signup and view all the answers

Flashcards

Problem Solving

For every problem, we can often find an algorithm that solves it.

Decision Problem

A problem where the answer is either yes or no.

Worst-Case Time

Measuring an algorithm's efficiency by considering the worst-case scenario time complexity.

P (Polynomial Time)

All problems for which there exists an algorithm with a time complexity of O(n^c) for some constant c > 0.

Signup and view all the flashcards

Hamilton Cycle

There is a cycle in the network that visits all nodes exactly once.

Signup and view all the flashcards

AKS Primality Test (2002)

Primes is in P, meaning primality testing can be done in polynomial time.

Signup and view all the flashcards

NP (Nondeterministic Polynomial Time)

Problems where, if the answer is yes, there is a proof that can be verified in polynomial time.

Signup and view all the flashcards

Hamiltonian Path in NP

If the answer is yes, there is a proof that can be verified in polynomial time. Hamiltonian Path is NP.

Signup and view all the flashcards

co-NP

Problems where, for the 'no' answer, there exists a proof that can be verified in polynomial time.

Signup and view all the flashcards

N is not prime

Every number that isn't prime has 2 numbers higher than 2 that it can be divided by.

Signup and view all the flashcards

CircuitSAT

CircuitSAT is in NP

Signup and view all the flashcards

P and NP

All problems in P are also in NP

Signup and view all the flashcards

Study Notes

Greining Reiknirita: P og NP

The text discusses the analysis of algorithms, focusing on the complexity classes P and NP
It's attributed to Páll Melsted in 2025.

P

For every problem, there is often an algorithm that solves the problem.
It introduces the concept of decision problems, problems for which the answer is either yes or no.

Defining "P"

P is a complexity class
If an algorithm for a problem exists, the worst-case time measures how long the algorithm takes to complete.
T(u) = max {time spent to read A}, where A is a case at size n.
n is typically the number of nodes in a network or the number of bits needed to represent G.

P (Polynomial Time)

P includes all problems for which there is an algorithm with T(n) = O(n^c), where c is a constant greater than 0
This means the running time is polynomial
All the problems are in P

Euler vs Hamilton

A graph G = (V, E) is given with n nodes and O(n²) edges.
The task is to find if there's a circuit/ring in the network that goes through all the nodes (Hamilton) or every edge (Euler) exactly once.
Euler has a "simple" algorithm that decides on a polynomial time O(|V| + |E|).
Hamilton, why not a brute force approach?
- Testing all combinations results in (n-1)!
n! >= 2^n, so that isn't possible.

Frumtölur (Prime Numbers)

The prime numbers problem: Given a number N, is it a prime number?
For i = 2 to √N, if N % i == 0, return False. - Return True.
The time complexity is √N
n = log₂(N) bits are the size of N
- √N = N^(1/2) = (2^(log₂(N)))^(1/2) = (2^n)^(1/2) = 2^(n/2)
Primes is in P ((AKS 2002))

NP

NP includes all problems where, if the answer is yes, there is proof that can be verified in polynomial time.
The Hamilton path problem is in NP
- Given a graph G = (V, E), is there a path through v₁,..., vₙ, where vᵢ ≠ vⱼ for i ≠ j, and (vᵢ, vᵢ₊₁) ∈ E?
- n is the number of nodes; verify all nodes for different solutions.
co-NP is the same, except that the "no" answers have a proof.

Primes and NP

Primes are in co-NP: If N is not prime, then there exist a, b >= 2 such that N = a * b
The proof (witness, Kvittun) is a, b, which, when multiplied, result in N
- a and b each have n bits to calculate the result
- O(n²) time makes verification possible
Therefore, primes are in both NP and co-NP.

Relationship Between P and NP

All problems in P are also in NP.
If the decision A is in P, then there is an algorithm R that calculates in polynomial time that solves A.
If an instance of A is yes, the witness is Ø (empty set), which verifies using R.
P ⊆ NP, P ⊆ co-NP

CircuitSAT

The input is a circuit K that takes in bit inputs x₁, ..., xₙ.
Task is: Are there values for the bits x₁ = a₁, ..., xₙ = aₙ that give the answer 1?
This is in NP.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Algorithm Analysis: P and NP

Choose a study mode

Podcast

Questions and Answers

Hvað er átt við með ákvörðunarverkefni í samhengi við reiknirit?

Hvernig er tímaflækja reiknirits oftast mæld?

Hvað táknar $T(n)$ í samhengi við reiknirit?

Hvað er átt við með 'margliðutíma' í flækjugreiningu reiknirita?

Hvað þýðir það ef verkefni er í flokknum P ('polynomial time')?

Hver er munurinn á Euler hring og Hamilton hring í grafi?

Hvers vegna er 'brute force' aðferðin ekki talin hagkvæm leið til að finna Hamilton hring í stóru grafi?

Hver er munurinn á því að ákvarða hvort tiltekið graf inniheldur Euler hring á móti Hamilton hring?

Gefin tala $N$, hver er tímaflækjan við að athuga hvort $N$ sé frumtala með því að deila í hana með öllum tölum frá 2 upp í $\sqrt{N}$?

Hvað er átt við með 'stærð inntaks' þegar tala $N$ er gefin sem inntak í reiknirit?

Hver er áætluð stærð í bitum fyrir tölu $N$?

Ef reiknirit hefur tímaflækju $O(\sqrt{N})$, og stærð inntaks er $n = \log_2(N)$, hver er þá tímaflækjan í tilliti til $n$?

Hvað þýðir það að verkefni sé í flokknum NP?

Ef Hamilton-leið er í NP, hvað þýðir það?

Hvað einkennir co-NP flokkinn?

Ef tala $N$ er ekki frumtala, hvað felur sönnun þess í sér?

Hvað er átt við með því að frumtölur séu í bæði NP og co-NP?

Hvað felur í sér að öll verkefni í P eru einnig í NP?

Ef verkefni A er í P, hvað þýðir það fyrir sönnun á tilviki af A?

Hvað er CircuitSAT verkefnið?

Ef CircuitSAT er í NP, hvað þýðir það?

Hver er munurinn á P og NP vandamálum?

Hver er skilgreiningin á NP-fullkomnum (NP-complete) vandamálum?

Hvað myndi það þýða ef sýnt væri fram á að P = NP?

Hver er helsti munurinn á ákvörðunarvandamáli (decision problem) og hagræðingarvandamáli (optimization problem)?

Hvaða fullyrðing er sönn um samband P, NP og NP-fullkominna vandamála?

Hvað er 'reducible' í samhengi við flækjustig NP vandamála?

Hver er munurinn á flækjustiginu $O(n)$ og $O(2^n)$?

Hver af eftirfarandi fullyrðingum er sönn um samband NP og co-NP?

Hvað er átt við með heildsölu reikniriti (heuristic algorithm)?

Af hverju er dulkóðun mikilvæg í nútíma tölvunarfræði?

Hver er helsta áskorunin við að takast á við NP-fullkomin vandamál í raunveruleikanum?

Hvað er átt við með 'approximationsreiknirit' (approximation algorithm)?

Ef þú ert með NP-fullkomið vandamál, hvaða aðferðir gætir þú notað til að takast á við það?

Flashcards

Problem Solving

Decision Problem

Worst-Case Time

P (Polynomial Time)

Hamilton Cycle

AKS Primality Test (2002)

NP (Nondeterministic Polynomial Time)

Hamiltonian Path in NP

co-NP

N is not prime

CircuitSAT

P and NP

Study Notes

Greining Reiknirita: P og NP

P

Defining "P"

P (Polynomial Time)

Euler vs Hamilton

Frumtölur (Prime Numbers)

NP

Primes and NP

Relationship Between P and NP

CircuitSAT

Studying That Suits You

Related Documents

More Like This

Groups versus Teams

P versus NP Problem

Algorithms: P and NP

Computational Complexity Theory