quiz 6

what does polynomial-time mean

O(n^k)

true or false: problems that can be solved in polynomial time belong to NP complexity class

true

if a problem’s solutions can be verified in __, the complexity class is NP (nondeterministic polynomial class)

polynomial time

true or false: All problems in P are not in NP

false

algorithmica is __

P=NP

heuristica is

NP problems are hard in worst case but easy on average

pessiland is __

NP problems are hard in some case but easy on at least some

minicrypt is __

one-way functions exist but we do not have public key cryptography

cryptomania is

public-key cryptography is possible

determining whether a graph has a hamiltonian cycle is __

np-complete

on the graph on the quiz, what did the edges mean

showing each NPC problem in the graph can be reduced to its parent

what does the spawn keyword in parallelization mean

allows a function call to run in parallel, but it does not have to run in parallel

what decides if a function runs in parallel if the spawn keyword is used?

a scheduler

what does the sync keyword do

waits for spawned process to complete before the code continues

what is work

runtime with only one processor available

what is span

minimum amount of runtime required from the start to end of program execution when there is no limit on the number of processors available

what is work law

span >= work / number of processors

what is span law

span >= work unlimited processors available

how do you calculate parallelism using work and span?

work / span

what is a maximum bipartite matching

matching with a maximum number of edges