Início / coding / Perguntas / 79529322
Accepted
Naseiva Juman
Asked: 2025-03-24 01:05:03 +0800 CST

Instâncias de subconjunto-soma requerem inerentemente números inteiros grandes para forçar dificuldade exponencial?

  • 772

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
python

2 respostas

  1. Best Answer

    Sabemos que a soma de subconjuntos pode ser resolvida em tempo pseudopolinomial . "Tempo pseudopolinomial" significa que o pior caso de tempo de execução em entradas grandes é limitado por um polinômio no comprimento da entrada e o maior valor numérico na entrada . Como uma sequência de Lbits pode codificar números de tamanho O(2^L), algoritmos de tempo pseudopolinomial realmente levam tempo exponencial (ou seja, exponencial no comprimento da entrada), mas algoritmos de tempo pseudopolinomial ainda são considerados melhores do que algoritmos de tempo exponencial "usuais", pois você pode evitar o comportamento exponencial se usar apenas números pequenos.

    Por exemplo, até mesmo este algoritmo simples para subconjunto-soma:

    def exists_subset_sum(num_set, target):
  reachable = {0}
  for num in num_set: reachable |= {prev + num for prev in reachable}
  return target in reachable

    tem tempo de execução pseudopolinomial. A observação principal é que o reachableconjunto contém apenas valores no intervalo [-i*M, i*M]na iiteração th, onde Mé max(abs(n) for n in num_set)). Então, o tamanho do conjunto é sempre O(L*M)(onde Lé o tamanho da entrada em bits) e as operações nele levam tempo polinomial em Le M, então todo o algoritmo leva tempo polinomial em Le M. Tecnicamente, como Mé exponencial em L, a complexidade de tempo de exists_subset_sumem termos de apenas Lé exponencial. Mas, você só pode obter o comportamento exponencial se deixar Mcrescer exponencialmente. Se você apenas aumentar Lsem aumentar, Mobterá, na pior das hipóteses, crescimento polinomial.

    Você notará que muitos algoritmos para resolver somas de subconjuntos também são pseudopolinomiais.

    • 4

  2. Parte do que pode estar confundindo você é que esse problema é difícil porque, ao decidir o que é NP ou não, o tamanho dos inteiros é medido em bits, não no valor. Dadas k entradas com um valor máximo de N, é bem fácil resolver o problema em tempo polinomial para kN. Muitos cientistas da computação receberam artigos mostrando que P = NP porque as pessoas acham que resolveram esse problema.

    O "tamanho" de um inteiro Né lg(N), não N. Para este problema em particular, a complexidade do pior caso depende do número de entradas e do tamanho total (em bits) de todas as entradas. Problemas difíceis exigem muitas entradas ou entradas longas.

    Tente usar 100 números aleatórios de 100 bits como entrada e faça com que seu alvo seja metade da soma deles.

    • 2

relate perguntas