Firstly, we define A and B as two decision problems with the same set of inputs.

Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for A and for B. The output is to decide if A(x) = Yes and B(x) = Yes. For example, in the "Independent Set AND Vertex Cover" problem, we must decide if G has an independent set of size >= k and a vertex cover of size <= k.

Find two decision problems A and B with the same set of inputs such that both A and B are NP-complete, but "A AND B" is computable in polynomial time.

My first try is SAT and UNSAT - thinking of two decision problems that cancel themselves out since if one is true, the other automatically isn't. Thus, the conjunction would always be false. I know that the NP-complete problems are not closed under union/intersection I am just struggling to find examples. I am wondering if this example works/does not work and if there are any other specific examples that would work as A and B.

  • $\begingroup$ How do I go from saying that it's a 'language' to classsifying it as a 'decision problem' (how do I extrapolate this information for decision problems) $\endgroup$
    – Oluchi A
    Nov 16, 2023 at 23:32
  • $\begingroup$ Languages and decision problems are the same thing. The language associated with a problem contains all its "yes" instance. The problem associated with a language $L$ is that of deciding whether an input string $x$ is in $L$. $\endgroup$
    – Steven
    Nov 16, 2023 at 23:35
  • 1
    $\begingroup$ Let $L \subseteq \{0,1\}^*$ be your favorite NP-complete language. Define $A = \{0x \mid x \in L\}$ and $B = \{ 1x \mid x \in L \}$. It is easy to show that $A$ and $B$ are both NP-complete (hint: show a Karp reduction from $L$). However $A \cap B = \emptyset$, which cannot be NP-complete (regardless of the P vs NP matter) since $\{0,1\}^*$ is in P but cannot be reduced to $\emptyset$. "SAT and UNSAT" does not necessarily work, since UNSAT is co-NP-complete and we don't know whether NP = co-NP. $\endgroup$
    – Steven
    Nov 16, 2023 at 23:48
  • $\begingroup$ en.wikipedia.org/wiki/Formal_language, en.wikipedia.org/wiki/Decision_problem $\endgroup$
    – D.W.
    Nov 16, 2023 at 23:52