Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
3answers
196 views

What kind of SAT am I dealing with here?

Problem set up: I have a long list of variables, $v_i$ (say about 200 total). I am given a bunch of Boolean statements as follows: $$\omega_1\land \omega_2\land \omega_3\land \omega_4\land \omega_5 ...
5
votes
0answers
113 views

Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...
9
votes
1answer
165 views

How hard is Heyting satisfiability, i.e. the constructive version of SAT? In particular, is 2-HSAT NL-complete or is it harder?

First of all, is it clear what I mean by $k$-HSAT? I'm assuming that for $k>2$, $k$-HSAT is NP-complete, but the details of the reductions between $k$-HSAT and $k$-SAT aren't obvious to me. I'm ...
0
votes
2answers
200 views

Generating 3SAT circuit for Integer factorization example

I read somewhere that 3SAT can be used to solve Integer Factorization. If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...
12
votes
6answers
1k views

SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
0
votes
1answer
252 views

Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...
1
vote
0answers
76 views

Deciding / Approximating Parity of Small Depth Decision Trees

Let C be a circuit such that: C: $\{0,1\}^n$ to $\{0,1\}$ the top most gate is a parity gate all the inputs to the parity gate are small depth decision trees there is a total of $2^{ log^k n}$ ...