User Giorgio Camerani

36 votes

3 answers

4k views

Consequences of Factoring being in P?

asked Feb 23, 2011 at 14:23

34 votes

2 answers

2k views

Consequences of $SAT \in BQP$

asked Apr 18, 2011 at 12:53

26 votes

3 answers

2k views

Consequences of #P = FP

asked Oct 8, 2010 at 7:14

21 votes

10 answers

3k views

#SAT Solver download

asked Sep 14, 2010 at 14:05

21 votes

5 answers

3k views

Reasons for which a graph may be not $k$ colorable?

asked Nov 21, 2012 at 22:09

19 votes

3 answers

2k views

Shortest Equivalent CNF Formula

asked Jan 21, 2012 at 13:40

18 votes

5 answers

692 views

Unique $k$-SAT benchmarks

asked Sep 11, 2013 at 21:41

17 votes

2 answers

931 views

Lower bounds on #SAT?

asked Sep 7, 2010 at 15:07

15 votes

4 answers

2k views

Counting the number of vertex covers: when is it hard?

asked Feb 12, 2011 at 17:27

14 votes

2 answers

1k views

0-1 Linear Programming: computing the Optimal Formulation

asked Dec 4, 2012 at 13:52

13 votes

2 answers

1k views

Counting solutions of Monotone-2CNF formulas

asked Oct 11, 2010 at 7:13

12 votes

1 answer

400 views

Measuring the randomness of CNF formulas

asked Jan 31, 2011 at 14:26

12 votes

1 answer

940 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

asked Sep 6, 2014 at 14:22

12 votes

1 answer

1k views

Consensus on P = NP in a world where RP = NP

asked Jan 20, 2013 at 17:29

11 votes

3 answers

799 views

Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

asked Apr 7, 2016 at 18:55

10 votes

2 answers

472 views

Compactly representing the solution set of a SAT instance

asked Oct 12, 2010 at 18:34

10 votes

2 answers

555 views

Amplitude of Random Cubic Graphs

asked Dec 15, 2011 at 15:13

9 votes

2 answers

541 views

The ODD EVEN DELTA problem

asked Sep 2, 2012 at 15:31

9 votes

1 answer

532 views

Help on the following combinatorial problem?

asked Sep 26, 2011 at 18:26

9 votes

2 answers

2k views

Reducing #SAT to #MONOTONE-2SAT

asked Sep 13, 2010 at 8:38

9 votes

2 answers

690 views

Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)

asked Apr 5, 2013 at 21:07

8 votes

2 answers

556 views

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

asked May 17, 2015 at 7:26

8 votes

1 answer

336 views

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

asked Nov 20, 2020 at 13:45

8 votes

2 answers

547 views

Using SAT for Computer Vision tasks

asked Oct 1, 2010 at 10:27

8 votes

2 answers

3k views

Monotone-2SAT and Vertex Cover

asked Sep 14, 2010 at 16:40

7 votes

2 answers

586 views

SAT Solution Space - Definition of Cluster of Solutions

asked Sep 9, 2010 at 9:03

7 votes

1 answer

309 views

Determining Graph Hulls

asked Mar 4, 2011 at 13:51

7 votes

4 answers

1k views

Trees: complexity of counting the number of vertex covers

asked Mar 19, 2011 at 18:45

7 votes

1 answer

428 views

Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

asked Jan 15, 2013 at 18:03

7 votes

2 answers

310 views

How hard is counting the number of vertex covers after a small perturbation?

asked Apr 14, 2011 at 14:06

Stack Exchange Network

55 Questions

Consequences of Factoring being in P?

Consequences of $SAT \in BQP$

Consequences of #P = FP

#SAT Solver download

Reasons for which a graph may be not $k$ colorable?

Shortest Equivalent CNF Formula

Unique $k$-SAT benchmarks

Lower bounds on #SAT?

Counting the number of vertex covers: when is it hard?

0-1 Linear Programming: computing the Optimal Formulation

Counting solutions of Monotone-2CNF formulas

Measuring the randomness of CNF formulas

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

Consensus on P = NP in a world where RP = NP

Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

Compactly representing the solution set of a SAT instance

Amplitude of Random Cubic Graphs

The ODD EVEN DELTA problem

Help on the following combinatorial problem?

Reducing #SAT to #MONOTONE-2SAT

Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

Using SAT for Computer Vision tasks

Monotone-2SAT and Vertex Cover

SAT Solution Space - Definition of Cluster of Solutions

Determining Graph Hulls

Trees: complexity of counting the number of vertex covers

Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

How hard is counting the number of vertex covers after a small perturbation?