La variante del sottoinsieme-somma ha un algoritmo $ o (1) $ se $ Goldbach $ è vero

Question

Dato $ s $ di numeri interi positivi $> $ $ 1 $ C'è una combinazione con anche $ somma $ > $ 2 $ cioè non la somma di due numeri ?

$ somma $ = 10

$ s $ = $ [4,6] $

$ no $ ,

somma di due primes $ 5 + 5= 10 $ .

combinazione $ 4 + 6= 10 $

ha una classe $ o (1) $ algoritmo se Goldbach è vero (sempre output $ No $ ). Altrimenti, sembrerebbe essere np-completo perché richiederebbe la risoluzione del sottoinsieme.

domanda

Una riduzione di molte-one-one-one-one-snl="container di matematica"> $ sottoinsieme-somma $ lavoro per questo problema di decisione in Poly-Time?

Answer 1

Se c'è un numero finito di eccezioni alla congettura Goldbach, quindi è ancora solvibile in tempo lineare.

Si noti che esiste una probabilità diversa da zero che la congettura di Goldbach è falsa.Heuristicamente, la probabilità di un numero infinito di eccezioni è zero.