我正在开发自定义子集和算法，但遇到了一个令人费解的问题：如果不使用非常大的整数（例如，大于 2^22），似乎很难生成真正“硬”的子集和实例（即强制指数级的计算工作量）。
我特别想知道：
- 是否存在已知的子集和构造或实例生成器，可以可靠地强制指数复杂性 - 特别是针对常见的子集和算法或自定义启发式方法 - 仅使用中等大小的整数（≤2^22）？
- 子集和实例的难度是否本质上与所涉及的整数的大小相关，或者是否有可能纯粹通过数值结构和关系来创建计算困难的实例，即使数字较小？
就上下文而言，以下是我在生成潜在困难实例方面所做的一些尝试（欢迎反馈或改进）：
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