8

[Now that the question's been clarified I'll post my previous comment as an answer.] It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone, so will be satisfied by setting all remaining variables to True. (If you want to count the number of solutions, on the other hand, that might be harder.)


6

First, I agree w/ Ludwik & other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time algorithms computing a fixed function $f$) input-output relationship, and polynomial-time algorithms are just too varied to say that they must take a certain ...


5

I would imagine it very difficult to prove that "[a] certain type of gadget must exist for a reduction from 3-SAT to X". You could state that one type of gadget would enable a specific reduction, or even a family of reductions, but there might still be a different reduction possible that you haven't thought of. If you could indeed prove that every ...


4

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict subclass of $\mathrm{EXP^{NP}}$ (which is the exponential analogue of $\Delta^P_2$). $\Theta^{\exp}_2$ can be variously defined as $$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=...


2

Your (self) answer is ok, but you can also build a reduction in which there is no "trivial" solution. Start from $X = \{ x_{1}, \ldots, x_{n} \}, x_i > 0$ with target sum $K$ and build: $X' = \{ 8 * x_{1}, \ldots, 8 * x_{n} \} \cup \{ 1, 1, 2 \}$ and target sum $K' = 8*K + 2$ In this case in order to solve the new problem $\langle X', K' \...


1

This doesn't quite answer your question because you're asking specifically about diagonal entries (in what basis? Any basis will work for the connection to immanents, but the complexity could change depending on what basis you use to actually compute $D_{ii}^\lambda$), but it's a little too long for a comment. Bürgisser showed that $(g,v) \mapsto D^{\lambda}(...


1

Let's define what P$^A$ means in the promise setting: A language L is in P$^A$ if there is a polytime oracle machine $M$ such that for all sets $B$ such that $B$ contains $A_{YES}$ and $B\cap A_{NO}=\emptyset$, $L=L(M^B)$. In other words, the polytime machine can ask queries that are not part of the promise but its output cannot depend on whether those ...


1

Yes, this appears to be true in the case that the integers are all positive. We simply take a Subset Sum instance defined by the set $ X = \{ x_{1}, \ldots, x_{n} \} $ and the target value $ K $ and create the set $ X' = X + \{ K \} $. Then there are at least two solutions to this problem if there is at least one to the original. Likewise, if there are two ...


Only top voted, non community-wiki answers of a minimum length are eligible