# hard problems

bad   hard   knap:bf   knap:dp   knap:dpv   set cover   sat

## hard problems

for many problems, no known polytime algorithm

recent news

## 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 ? ? ?

## 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) )

• 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

## 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[j] = 0
A[val] = wt  # 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 ?

## 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 - * - - - - * - - * * - * - - - * - * -
```

## 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
```