$ GOLDBACH $がtrueの場合、サブセットSUMの亜種には$ O（1）$アルゴリズムがあります。

Question

与えられた $ s $ の正の整数 $> $ $ 1 $ は、 ine $ sum $ >> $ 2 $の組み合わせがあります。 それは not 2つの PRIMES ？

の合計です。

$ sum $ = 10

$ s $ = $ [4,6] $

$ no $ 、

2つのプライムの合計 $ 5 + 5= 10 $ 。

組み合わせ $ 4 + 6= 10 $

GOLDBACH はtrueです（ $ no $ を出力します）。それ以外の場合は、サブセット和を解く必要があるため、NP完成しているようです。

質問

は、この決定問題に対する $サブセット$ からの多重縮小をしますか？

Answer 1

ゴールドバッハ推測に有限の例外がある場合は、まだ線形時間で解決可能です。

Goldbachの推測が偽のゼロ以外の確率があることに注意してください。ヒューリスティックには、無限数の例外の可能性はゼロです。