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

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