User Giorgio Camerani

102 votes

Accepted

Why is 2SAT in P?

answered Jun 6, 2011 at 20:58

32 votes

Algorithms from the Book

answered Oct 1, 2010 at 9:45

18 votes

What papers should everyone read?

answered Oct 15, 2010 at 16:04

16 votes

What are the #P-complete subfamilies of #2-SAT?

answered Nov 29, 2012 at 14:02

15 votes

What papers should everyone read?

answered Oct 15, 2010 at 16:11

14 votes

Minimum Unsatisfiable 3-CNF Formulae

answered Sep 30, 2011 at 18:25

14 votes

Accepted

How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP?

answered Jul 23, 2012 at 12:59

11 votes

Why is CNF used for SAT and not DNF?

answered Sep 17, 2010 at 15:48

10 votes

Surprising Results in Complexity (Not on the Complexity Blog List)

answered Sep 9, 2010 at 10:28

9 votes

Accepted

The ODD EVEN DELTA problem

answered Jan 1, 2013 at 9:14

7 votes

Open or Interactive Constraint Satisfaction

answered Oct 19, 2010 at 13:22

6 votes

Is embedding a solution feasible for SAT?

answered Sep 17, 2010 at 12:09

6 votes

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

answered Jun 9, 2013 at 7:38

6 votes

Why is CNF used for SAT and not DNF?

answered Sep 6, 2013 at 21:51

6 votes

Accepted

Determining Graph Hulls

answered Mar 4, 2011 at 19:54

4 votes

Network / Social network analysis visualization tools?

answered Mar 18, 2011 at 20:59

4 votes

Grid $k$-coloring without monochromatic rectangles

answered Mar 22, 2011 at 16:43

4 votes

What are the best current lower bounds on 3SAT?

answered Sep 7, 2010 at 14:45

4 votes

What are some career options for someone with a computer scientist master degree?

answered Nov 12, 2010 at 13:08

2 votes

Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

answered Jul 26, 2012 at 17:05

2 votes

Relationship between symmetry and computational intractability?

answered Sep 8, 2010 at 12:11

2 votes

Where do I turn for help with research/publishing?

answered Oct 7, 2010 at 7:55

1 vote

Monotone-2SAT and Vertex Cover

answered Sep 20, 2010 at 12:53

1 vote

What is the recommended software for drawing data structures such as graphs and trees?

answered Nov 7, 2012 at 12:48

1 vote

Accepted

Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

answered Jan 20, 2016 at 7:42

1 vote

Hamiltonian cycle vs co-NP

answered Jan 2, 2019 at 19:43

0 votes

$⊕P$-completeness of $⊕2SAT$

answered Jan 28, 2021 at 19:49

-2 votes

Are there analogous works to PPSZ algorithm for #P?

answered Feb 20, 2021 at 18:34

Stack Exchange Network

28 Answers

Why is 2SAT in P?

Algorithms from the Book

What papers should everyone read?

What are the #P-complete subfamilies of #2-SAT?

What papers should everyone read?

Minimum Unsatisfiable 3-CNF Formulae

How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP?

Why is CNF used for SAT and not DNF?

Surprising Results in Complexity (Not on the Complexity Blog List)

The ODD EVEN DELTA problem

Open or Interactive Constraint Satisfaction

Is embedding a solution feasible for SAT?

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

Why is CNF used for SAT and not DNF?

Determining Graph Hulls

Network / Social network analysis visualization tools?

Grid $k$-coloring without monochromatic rectangles

What are the best current lower bounds on 3SAT?

What are some career options for someone with a computer scientist master degree?

Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

Relationship between symmetry and computational intractability?

Where do I turn for help with research/publishing?

Monotone-2SAT and Vertex Cover

What is the recommended software for drawing data structures such as graphs and trees?

Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

Hamiltonian cycle vs co-NP

$⊕P$-completeness of $⊕2SAT$

Are there analogous works to PPSZ algorithm for #P?