Estou desenvolvendo algoritmos personalizados de soma de subconjuntos e me deparei com um problema intrigante: parece difícil gerar instâncias de soma de subconjuntos realmente "difíceis" (ou seja, forçando esforço computacional exponencial) sem usar números inteiros muito grandes (por exemplo, maiores que cerca de 2^22).
Gostaria de saber especificamente:
- Existem construções conhecidas ou geradores de instâncias para soma de subconjuntos que forçam de forma confiável a complexidade exponencial — particularmente contra algoritmos comuns de soma de subconjuntos ou heurísticas personalizadas — usando apenas inteiros de tamanho moderado (≤2^22)?
- A dificuldade das instâncias de subconjunto-soma está inerentemente ligada ao tamanho dos números inteiros envolvidos ou é possível criar instâncias computacionalmente difíceis puramente por meio de estruturas e relacionamentos numéricos, mesmo com números menores?
Para contextualizar, aqui estão algumas tentativas que fiz para gerar instâncias potencialmente difíceis (feedback ou melhorias são bem-vindos):
import random
def generate_exponential_instance(n):
max_element = 2 ** 22
A = [random.randint(1, max_element) for _ in range(n)]
while True:
mask = [random.choice([0, 1]) for _ in range(n)]
if sum(mask) != 0:
break
target = sum(A[i] * mask[i] for i in range(n))
return A, target
def generate_dense_high_values_instance(n):
base = 2 ** 22 - random.randint(0, 100)
A = [base + random.randint(0, 20) for _ in range(n)]
target = sum(random.sample(A, k=n // 2))
return A, target
def generate_merkle_hellman_instance(n, max_step=20):
total = 0
private_key = []
for _ in range(n):
next_val = total + random.randint(1, max_step)
private_key.append(next_val)
total += next_val
q = random.randint(total + 1, 2 * total)
r = random.randint(2, q - 1)
public_key = [(r * w) % q for w in private_key]
message = [random.randint(0, 1) for _ in range(n)]
ciphertext = sum(b * k for b, k in zip(message, public_key))
return public_key, ciphertext