# jemdoc: addcss{rbh.css}, addcss{jacob.css} = hard problems ~~~ {}{raw} bad   hard   knap:bf   knap:dp   knap:dpv   set cover   sat   ~~~ #~~~ #{}{raw} #

## baby, you with the bad boys now

#~~~ # #~~~ #from Out of Sight by Elmore Leonard #~~~ ~~~ {}{raw}

## hard problems

~~~ ~~~ for many problems, no known polytime algorithm - [https://en.wikipedia.org/wiki/Graph_isomorphism graph isomorphism] - [https://en.wikipedia.org/wiki/Knapsack_problem 0-1 knapsack] - [https://en.wikipedia.org/wiki/Set_cover_problem set cover] - [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem satisfiability] ~~~ ~~~ {recent news} - [https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem graph iso in quasi-poly time ?] - [https://en.wikipedia.org/wiki/Time_complexity\#Quasi-polynomial_time time complexity] ~~~ ~~~ {}{raw}

## 0-1 knapsack: brute force

~~~ ~~~ for each subset - if weight ok and value best-so-far -- print subset, update best-so-far-value ~~~ ~~~ {}{} def powerset(iterable): # all subsets #https://docs.python.org/2/library/itertools.html#recipes "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) def bruteforce(n,val,wt,W): indices = range(n) # [0 1 .. n-1] bestVal = 0 for indexset in powerset(indices): v, w = 0, 0 for t in indexset: v+= val[t] w+= wt[t] if w <= W and v > bestVal: bestVal = v print indexset, w, v ~~~ ~~~ {brute force 0-1 knapsack} runtime ? - {{ Ω(2n) }} correct ? - yes: considers every subset can we do better ? ? ? ~~~ ~~~ {}{raw}

## 0-1 knapsack: dynamic programming

~~~ ~~~ subproblems ? - by set of allowed items - by allowed total weight set of allowed items ? - {{ {1}   {1 2}   {1 2 3}   ... }} allowed total weight ? - {{ 0   1   2   ... }} {{K[w][j]}}: best value with items {{1..j}}, total wt {{≤}} w compute {{K[w][j]}} - item j out? value {{K[w][j-1]}} - item j in? value {{K[w-w_j][j-1] + v_j}} - so set {{K[w][j]}} to max of these two ~~~ ~~~ {0-1 knapsack: dp}{} #python indexing: val[t],wt[t] corresponds to K[][t+1] def solveknapsack(val,wt,W): n = len(val) K = [[0 for j in xrange(n+1)] for w in xrange(W+1)] for j in range(1,n+1): for w in range(W+1): if wt[j-1]>w: K[w][j] = K[w][j-1] else: K[w][j] = max(K[w][j-1], K[w-wt[j-1]][j-1]+val[j-1]) ~~~ ~~~ {0-1 knapsack: dp example}{} val [ 6, 9, 7, 9, 8, 7] wt [11, 6, 8, 10, 8, 9] max value knapsack, weight at most 27 ? 0 [0, 0, 0, 0, 0, 0, 0] 1 [0, 0, 0, 0, 0, 0, 0] 2 [0, 0, 0, 0, 0, 0, 0] 3 [0, 0, 0, 0, 0, 0, 0] 4 [0, 0, 0, 0, 0, 0, 0] 5 [0, 0, 0, 0, 0, 0, 0] 6 [0, 0, 9, 9, 9, 9, 9] 7 [0, 0, 9, 9, 9, 9, 9] 8 [0, 0, 9, 9, 9, 9, 9] 9 [0, 0, 9, 9, 9, 9, 9] 10 [0, 0, 9, 9, 9, 9, 9] 11 [0, 6, 9, 9, 9, 9, 9] 12 [0, 6, 9, 9, 9, 9, 9] 13 [0, 6, 9, 9, 9, 9, 9] 14 [0 ? ? ? ? ? ?] 14 [0, 6, 9, 16, 16, 17, 17] 15 [0, 6, 9, 16, 16, 17, 17] 16 [0, 6, 9, 16, 18, 18, 18] 17 [0, 6, 15, 16, 18, 18, 18] 18 [0, 6, 15, 16, 18, 18, 18] 19 [0, 6, 15, 16, 18, 18, 18] 20 [0, 6, 15, 16, 18, 18, 18] 21 [0, 6, 15, 16, 18, 18, 18] 22 [0, 6, 15, 16, 18, 24, 24] 23 [0, 6, 15, 16, 18, 24, 24] 24 [0, ? ? ? ? ? ?] 24 [0, 6, 15, 16, 25, 26, 26] 25 [0, 6, 15, 22, 25, 26, 26] 26 [0, 6, 15, 22, 25, 26, 26] 27 [0, 6, 15, 22, 25, 26, 26] ----------------------------- solution 24 [0, 1, 0, 1, 1, 0] val 26 ~~~ ~~~ {dp knapsack wc superpoly} - consider these instances -- each value and weight has n bits, so in {{[ 2n-1 ... 2n -1 ]}} -- average weight {{  ( 2n-1+2n -1 ) / 2   ≈   .75 2n}} -- let W be n times average weight, so {{  ≈ .75 n 2n}} -- input size {{  Θ( n2 )   }} bits - brute force wc time -- {{2n}} subsets, wc {{Θ(n)}} weights, each {{Θ(n)}} bits -- total {{  Θ( n2 2n )}} - dyn. prog. wc time -- {{Θ( nW )   =   Θ( n n 2n )   =   Θ( n2 2n )}} - let {{  t = n2   so n = √ t     let f(t) = t 2√t}} -- each alg. input {{  Θ( t ) bits   }} wc time {{  Θ( f(t) )}} - [https://en.wikipedia.org/wiki/Time_complexity\#Table_of_common_time_complexities time complexities] - {{2O(log t)}} polynomial - {{2o(t)}} subexponential - {{2Ω(t)}} exponential - here -- {{ limt → ∞ ( 2k log t / f(t) ) = 0,  }} so f(t) superpoly -- {{ limt → ∞ ( f(t) / 2t ) = 0,  }} so f(t) subexp ~~~ ~~~ {}{raw}

## 0-1 knapsack: another DP solution

~~~ ~~~ - organizing subproblems by value (instead of weight) - useful in constructing knapsack PTAS (polytime approx scheme) ~~~ ~~~ {}{} def knapDPV(val,wt,V): #dynamic programming by value # A[v][j] is min weight of subset of items 0..j with exact val v infinity = 1 + sum(val) #larger than any possible sum of values n = len(val) A = [[infinity for j in xrange(n)] for v in xrange(V+1)] for j in range(n): A[0][j] = 0 A[val[0]][0] = wt[0] # end initialization for v in range(1,V+1): # row 0 already initialized for j in range(1,n): # column 0 " " new, subv = A[v][j-1], v-val[j] if subv >= 0: new = min(new, A[subv][j-1] + wt[j]) A[v][j] = new ~~~ ~~~ {knapsack DPV} - time in O(nV), so exponential because V can be big - correctness ? ~~~ ~~~ {}{raw}

## setcover

~~~ ~~~ {brute force set cover}{} from random import randint from itertools import chain, combinations def powerset(iterable): #https://docs.python.org/2/library/itertools.html#recipes "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) def settostring(s,n): # set as pretty binary string x = '' for j in range(n): if j in s: x += ' *' else: x += ' -' return x def gensubset(a,b,n): # subset of 0..n-1, each with prob a/b s = set() for j in range(n): if randint(1,b) <= a: s.add(j) return s def initsubsets(n,m,a,b): # m subs of 0..n-1 # an element in a subset with probability a/b L = [] # list of subsets for _ in range(m): L.append(gensubset(a,b,n)) sumlen = 0 for x in L: sumlen += len(x) print settostring(x,n) print 'universe size', n,' avg subset size', sumlen*1.0/m return L def bruteforce(n,m,L): indices = range(m) # [0 1 .. m-1] bestcover = () for indexset in powerset(indices): subsetunion = set() for t in indexset: subsetunion |= L[t] # indexsets sorted by cardinality, so first found is min if len(subsetunion) == n: print 'size', len(indexset), 'cover', indexset for j in indexset: print settostring(L[j],n) return # so return once one is found n,m,a,b = 40,25,2,11 L = initsubsets(n,m,a,b) bruteforce(n,m,L) ~~~ ~~~ {set cover example}{} set universe 0 1 2 3 4 5 6 7 8 9 0 - - * - - - - * * - 1 - * - - - - - * - * 2 - - - - * - - * * - 3 - - - - - - - - * - 4 - - - - - * - * * - 5 - - - - * - * * - * 6 * * - * - - - - - - 7 - - - - - - * * - - min cover (0, 4, 5, 6) 0 - - * - - - - * * - 4 - - - - - * - * * - 5 - - - - * - * * - * 6 * * - * - - - - - - ~~~ ~~~ {another example}{} set universe 0 1 2 3 4 5 6 7 8 910111213141516171819 0 * - * - - - * - * - - - - * - * - - * - 1 - - - * - * - * - - - * - - * * - - - - 2 - * - - - - * - * - - - - - - - - * - - 3 - - - * - - - - - - - - - - - - - - * - 4 * - - - - * - * - * - - - - - * - - - - 5 - - - * - - * * - - - - - * - * - - - - 6 - - - - - * - - * - - * * - - * - - * - 7 - * - - * - - - * - * * * - * * - - - - 8 - * - - * - - - * - - - - * * - - - * * 9 * - * - - - * * - - - - - - - - - - - * 10 - * - - - - * - - * * - * - - - * - * - min cover (0, 1, 2, 8, 10) 0 * - * - - - * - * - - - - * - * - - * - 1 - - - * - * - * - - - * - - * * - - - - 2 - * - - - - * - * - - - - - - - - * - - 8 - * - - * - - - * - - - - * * - - - * * 10 - * - - - - * - - * * - * - - - * - * - ~~~ ~~~ {}{raw}

## satisfiability

~~~ ~~~ given a boolean formula in CNF, is it satisfiable? assume input has n variables and m clauses brute force: {{2n}} possible assignments brute force: worst case time {{ O(m2n) }} ~~~ ~~~ {sat example}{} ( x1 or ~x2 or x3 ) and ( x1 or ~x2 or x4 ) and ( x1 or x2 or x3 ) and ( x1 or x2 or x4 ) and (~x1 or ~x2 or ~x3 ) and (~x1 or ~x2 or x3 ) and (~x1 or x2 or x4 ) and ( x2 or ~x3 or ~x4 ) and ( x2 or x3 or ~x4 ) [ 1, -2, 3] [ 1, -2, -4] [ 1, 2, 3] [ 1, 2, 4] [ -1, -2, -3] [ -1, -2, 3] [ -1, 2, 4] [ 2, -3, -4] [ 2, 3, -4] satisfiable (0, 1, 1, 0) ~~~ ~~~ {another example}{} [ -4, -5, 6] [ -4, 5, -6] [ -2, 4, -5] [ -2, 5, -6] [ -1, -3, -4] [ -1, -3, 4] [ -1, 4, -6] [ 1, -4, 5] [ 1, -3, -5] [ 1, -3, 4] [ 1, 5, -6] [ 2, 5, 6] [ 3, -5, -6] [ 4, -5, 6] [ 4, 5, -6] [ 4, 5, 6] satisfiable (1, 1, 0, 1, 0, 0) ~~~ ~~~ {brute force sat solver}{} # I/O: literals x1 -x1 x2 -x2 ... rept'd by 1 -1 2 -2 ... def clause_sat(clause,asnmt): for var in clause: if ((var>0 and asnmt[ var-1 ] == 1) or (var<0 and asnmt[-(var+1)] == 0)): return True return False def sat(formula, asnmt): for clause in formula: if not clause_sat(clause,asnmt): return False return True n, k, m = 20, 3, 90 #max m: (n choose k)(2^k) myf = formula(n,k,m) show(myf, False) allAsn = product([0,1],repeat=n) for a in allAsn: if sat(myf,a): print 'satisfiable', a ~~~