Un caso speciale di somma sottoinsieme

Question

Ho trovato il problema seguente nel mio corso di teoria della complessità:

Dato un set di numeri $ a:={a_1, \ dots, a_n \} \ sottoselezione _ {\ mathrm {finito}} \ mathbb {n} $ e un numero $ B $ anche in $ \ mathbb {n} $ Allo ad esempio che si applica la seguente condizione: $ a_i $ divide $ a_ {i + 1} $ per tutti i $ I e $ a_i .Dimostra che questo caso speciale di somma sottotesta è decidabile in p.

A causa della condizione data, $ B $ deve essere un multiplo della prima $ a \ neq 1 $.Prendendo $ a_1 \ neq 1: B= A_1 \ clot x $ .Trovare questo X mi riporta al problema del sottoinsieme, però che non è sicuramente in p.

Qualsiasi aiuto sarebbe apprezzato.

Answer 1

In breve, l'algoritmo avido funziona, dove in ogni passaggio trovi il numero più grande in $ a $ e sottrarlo da $ B $ . Se $ B $ diventa zero, ottieni una soluzione. Se raggiungi un punto in cui tutti i numeri in $ A $ sono maggiori di $ B $ output n. < / P >.

---

.

Nel seguente elenco una descrizione formale dell'algoritmo e una prova di correttezza.

Ecco una descrizione formale dell'algoritmo. Let $ A_0= A, B_0= B $ e $ B_i $ Sii il valore della $ B $ Dopo la $ i $ -th iteration. Let $ A_i $ Be I numeri rimasti in $ A $ dopo la $ I $ -th iteration. Quindi l'algoritmo va come segue. In ogni passaggio $ i= 1, \ punti $ trova il numero più grande $ a_j $ in $ a_ {i-1} $ non maggiore di $ B_ {i-1} $ . Se nessun numero tale esiste il numero di output. Altrimenti, impostare $ B_ {i}= B_ {i-1} - A_J $ e $ a_i= A_ {I- 1} \ setminus \ {a_j \} $ . Se $ B $ diventa uguale a zero, quindi output yes, altrimenti iterano.

rivendicazione 1. L'algoritmo precedente uscita la risposta corretta dell'istanza dettagliata del caso limitato delle somme di sottoinsieme descritta nella domanda.

Prima di provare la rivendicazione, dimostriamo un reclamo ausiliario.

rivendicazione 2. Let $ A_1, \ Dots a_n $ Be I numeri in $ A $ in ordine ascendente. Quindi $ \ Sum \ Limits_ {i= 1} ^ {k-1} A_i per tutti $ k \ in [n] $ .

Proof. (rivendicazione 2). Prova con induzione su $ k $ . Per n= 1, la somma è vuota. Ora lo dimostriamo per $ k $ . $$ \ Sum \ Limits_ {i= 1} ^ {k-2} A_I + A_ {K-1} <2A_ {I-1} \ Leq A_i, $$ . Laddove la prima disuguaglianza detiene a causa dell'ipotesi di induzione e il secondo detiene per assunzione da $ a_ {k-1} $ divide e è più piccola di $ a {k} $ .

Prova. (rivendicazione 1) Se l'algoritmo uscirà Sì, quindi è chiaramente un'istanza sì, poiché sceglie solo i numeri dai set dati e sottraibili da $ B $ .

Ora dimostriamo che, se il nostro algoritmo produce no, l'istanza data è un'istanza. A tal fine dimostriamo che se al passaggio $ i $ scegliamo un elemento $ a_j $ , quindi qualsiasi La soluzione dell'istanza data deve contenere questo elemento. Proviamo questo per induzione su $ i $ . Si noti che qualsiasi class class="container di matematica"> $ a_j ', j'> j $ è strettamente maggiore di $ B_i $ e quindi può Non essere mai incluso, supponendo per ipotesi di induzione, tutte le selezioni precedenti di $ A $ faceva una parte di una soluzione se esiste uno. Ora usando la rivendicazione 1, $ \ sum \ limits_ {i= 1} ^ {j-1} A_J $ < $ A_J $ e poiché rimuoviamo solo gli elementi, $ A_i $ non contiene altri elementi più piccoli di $ A_J $ E quindi, se non scegliamo $ A_J $ Scelta di tutti gli elementi più piccoli non sarà sufficiente per ottenere una somma uguale a $ B $ . Quindi, dobbiamo scegliere $ a_j $ .

Answer 2

Considerare il seguente caso speciale del tuo problema: $ a_i= c ^ {i-1} $ per alcuni $ c \ ge 2 $ .Ad esempio, se $ c= 10 $ , quindi abbiamo $ A_1= 1, A_2= 10, A_2= 100,A_3= 1000, \ Dots, A ^ N= c ^ {n-1} $ .

In questo caso, c'è una soluzione se e solo se $ 0 \ le b e la base $ c $ Rappresentazione della $ B $ non contiene cifre diverse da 0 e 1. In particolare, può esserci una soluzione anche per una classe="container di matematica"> $ B $ che non sono multipli di $ c $ , contraddicando il tuo secondo al precedente paragrafo.

Vedi se questo ti aiuta a pensare al problema.