これはプログラミングの問題というよりも数学の問題かもしれませんが、私はこれについてしばらく考えていて、これが解決可能な問題かどうかを判断するのに苦労しています.
私は次のものを持っています：
- シンボルのセットをソースとするセットA、B
- ブール関数F : A × B → {0,1}
集合 C = {(x,y) : x ∈ A, y ∈ B, with F(x,y) = 1} を構築したいと考えています。
( F は、任意のペアに対して O(1) で計算できます )
ここまでは、この計算は基本的に、F が定数時間の場合、O(|A| × |B|) で実行される関数 F を介した A × B のフィルターのみで構成されます。
しかし、私は私を助けることができると感じる C の 1 つのプロパティを知っています...
私はそれを知っています |C| << |A| |B| 、実際、私はかなり確信しています |C| |A|についてです . これを悪用する方法があるように感じます (私は最近、確率的アルゴリズムを紹介されましたが、これが役立つと感じていますが、確実にはわかりません)。
これを解決するには、いくつかの形式の補助構造が必要になると思いますが、構造がAのサイズの多項式のみである限り、それ自体はそれほど問題にはならないはずです(べき集合の計算は少し多いかもしれませんが、A はできます少し大きくなります）。
これは、ある種の下限の複雑さがあることが証明されているもののようにも感じますが、それを証明するための学術的知識は実際にはありません。
どのドメインを調べるべきかについてのガイダンスやヒントをいただければ幸いです。
これまで考えたこと：
これはSATの問題によく似ているようですが、私はそれらについてほとんど何も知りません
この問題は、セット識別の問題 (少なくとも... 2 つのセットの差を計算する) と少し似ているように感じます。ただし、この形式のトピックに関する調査を見つけることができません (「A を反復し、B を反復する」タイプの回答が多数得られるだけです)。