Un caso especial de suma de subconjunto.

Question

Me encontré con el siguiente problema en mi complejidad-teoría del curso:

Dado un conjunto de números $ a:={a_1, \ dots, a_n \ \ mathrm {finite}} \ mathbb {n} $ y un número $ b $ también en $ \ mathbb {n} $ que se aplica la siguiente condición: $ a_i $ divides $ a_ {i + 1} $ para todos $ I y $ A_I .Demostrar que este caso especial de subconjunto-suma es decidible en p.

Debido a la condición dada, $ b $ tiene que ser un múltiplo de la primera $ a \ neq 1 $.Tomando $ A_1 \ NEQ 1: B= A_1 \ CDOT X $ .Encontrar este X me lleva de vuelta al problema de la suma de subsetlenses, aunque seguramente no está en p.

Se apreciaría cualquier ayuda.

Answer 1

En resumen, el algoritmo codicioso funciona, donde en cada paso encuentra el número más grande en $ a $ y restálo de $ b $ . Si $ b $ se convierte en cero, obtiene una solución. Si llega a un punto donde todos los números en $ a $ son mayores que $ b $ Salida no. < / p>

---

En la siguiente, enumeré una descripción formal del algoritmo y una prueba de corrección.

Aquí hay una descripción formal del algoritmo. Deje que $ A_0= A, B_0= B $ y $ b_i $ sea el valor de $ b $ después del $ i $ iteración. Deje que $ A_I $ se queden en $ a $ después del $ i $ iteración. Luego el algoritmo va como sigue. En cada paso $ i= 1, \ puntos $ Encuentre el número más grande $ a_j $ en $ A_ {I-1} $ no es mayor que $ b_ {i-1} $ . Si no existe tal número de salida, no. De lo contrario, configure $ b_ {i}= b_ {i-1} - a_j $ y $ a_i= a_ {i- 1} \ setminus \ {A_J \} $ . Si $ b $ se vuelve igual a cero, entonces salida Sí, de lo contrario.

la reivindicación 1. El algoritmo anterior Salida La respuesta correcta de la instancia dada del caso restringido de las sumas de subconjunto descrito en la pregunta.

Antes de probar la reclamación, probamos un reclamo auxiliar.

la reivindicación 2. deja $ a_1, \ puntos A_n $ Sé los números en $ Un $ en orden ascendente. Luego $ \ sum \ limits_ {i= 1} ^ {k-1} A_I para todos $ k \ en [n] $ .

Prueba. (reivindicación 2). Prueba con inducción sobre $ k $ . Para n= 1, la suma está vacía. Ahora lo probamos para $ k $ . $$ \ SUM \ LIMITS_ {I= 1} ^ {K-2} A_I + A_ {K-1} <2A_ {I-1} \ Leq A_I, $$ donde se sostiene la primera desigualdad debido a la hipótesis de inducción y la segunda se mantiene al asunción desde $ a_ {k-1} $ divide y es más pequeño que $ a {k} $ .

Prueba (reivindicación 1) Si el algoritmo sale sí, entonces es claramente una instancia de sí, ya que solo elige los números de los conjuntos dados y restan los valores de $ b $ .

Ahora probamos que, si nuestro algoritmo sale no, la instancia dada es una instancia. Con este fin, demostramos que si en el paso $ i $ elegimos un elemento $ A_J $ , entonces La solución de la instancia dada debe contener este elemento. Probamos esto por inducción sobre $ i $ . Tenga en cuenta que cualquier $ A_J ', J'> J $ es estrictamente mayor que $ b_i $ y, por lo tanto, puede Nunca se puede incluir, asumiendo por hipótesis de inducción, todas las selecciones anteriores de $ a $ fueron parte de una solución si existe uno. Ahora usando la reivindicación 1, $ \ sum \ limits_ {i= 1} ^ {j-1} A_J $ < $ a_j $ y, dado que solo eliminamos elementos, $ a_i $ no contiene otros elementos más pequeños que $ a_j $ y, por lo tanto, si no elegimos $ A_J $ Elegir todos los elementos más pequeños no será suficiente para obtener una suma igual a $ b $ . Por lo tanto, tenemos que elegir $ A_J $ .

Answer 2

Considere el siguiente caso especial de su problema: $ A_I= C ^ {I-1} $ para algunos $ C \ GE 2 $ .Por ejemplo, si $ c= 10 $ , entonces tenemos $ A_1= 1, A_2= 10, A_2= 100,A_3= 1000, \ DOTS, A ^ N= C ^ {N-1} $ .

En este caso, hay una solución si y solo si $ 0 \ le b y la base $ C $ La representación de $ b $ no contiene dígitos distintos de 0 y 1. En particular, puede haber una solución incluso para algunas $ b $ que no son múltiples de $ C $ , contradeciendo su segundo párrafo.

Vea si esto le ayuda a pensar en el problema.