User Realz Slaw

22 votes

Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

answered Oct 13, 2013 at 0:21

22 votes

Is Dominosa NP-Hard?

answered Nov 15, 2013 at 7:28

18 votes

Proving that the conversion from CNF to DNF is NP-Hard

answered Sep 10, 2012 at 18:52

16 votes

Accepted

Tiling an orthogonal polygon with squares

answered Nov 7, 2013 at 19:35

14 votes

Accepted

What is "memory coalescing"?

answered Nov 21, 2013 at 21:08

14 votes

Accepted

Poly-time reduction from ILP to SAT?

answered Oct 14, 2013 at 22:33

11 votes

Accepted

Is there a repository for the hierarchy of proofs?

answered Sep 10, 2012 at 13:13

10 votes

Accepted

How can P =? NP enhance integer factorization

answered Nov 13, 2012 at 19:41

10 votes

Accepted

FFT-less $O(n\log n)$ algorithm for pairwise sums

answered Nov 3, 2013 at 8:12

10 votes

Accepted

Complexity of deciding the satisfiability of a quasi-monotone CNF formula

answered Oct 28, 2013 at 9:08

9 votes

Accepted

Is Dominosa NP-Hard?

answered Dec 10, 2013 at 4:28

9 votes

Computing set difference between two large sets

answered Nov 14, 2013 at 5:18

9 votes

Finding odd directed circuit

answered Sep 12, 2012 at 19:07

9 votes

What is the fastest algorithm for multiplication of two n-digit numbers?

answered Oct 20, 2013 at 3:19

8 votes

Accepted

Formulas for which any equivalent CNF formula has exponential length

answered Nov 27, 2013 at 14:51

7 votes

Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

answered Sep 30, 2013 at 17:58

7 votes

Accepted

Practical applications of disjoint set datastructure

answered Oct 25, 2012 at 20:05

7 votes

Comparing rational numbers

answered Nov 25, 2012 at 4:06

6 votes

A tentative satisfiability algorithm

answered Sep 12, 2012 at 22:48

6 votes

Accepted

Converting a 2-SAT formula into an implication graph

answered Oct 18, 2013 at 16:49

6 votes

Accepted

standard sequential algorithm with polylog runtime?

answered Nov 1, 2013 at 15:28

6 votes

Accepted

Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

answered Nov 11, 2013 at 22:12

6 votes

Is it possible to modify dijkstra algorithm in order to get the longest path?

answered Nov 13, 2013 at 7:43

6 votes

Accepted

Is MIN or MAX-True-2-XOR-SAT NP-hard?

answered Nov 4, 2013 at 2:13

6 votes

Accepted

CNF Generator for Factoring Problems

answered Nov 7, 2013 at 21:19

5 votes

Does the performance of matrix multiplication depend on the storage of the array?

answered Nov 10, 2013 at 5:02

5 votes

Minimal size of contracting a DAG into a new DAG

answered Oct 28, 2013 at 8:13

5 votes

Accepted

Metrics and algorithms for complexity of a graph

answered Oct 28, 2013 at 22:13

5 votes

How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

answered Sep 11, 2012 at 4:20

5 votes

Does every NP problem have a poly-sized ILP formulation?

answered Nov 18, 2012 at 22:33

Stack Exchange Network

71 Answers

Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

Is Dominosa NP-Hard?

Proving that the conversion from CNF to DNF is NP-Hard

Tiling an orthogonal polygon with squares

What is "memory coalescing"?

Poly-time reduction from ILP to SAT?

Is there a repository for the hierarchy of proofs?

How can P =? NP enhance integer factorization

FFT-less $O(n\log n)$ algorithm for pairwise sums

Complexity of deciding the satisfiability of a quasi-monotone CNF formula

Is Dominosa NP-Hard?

Computing set difference between two large sets

Finding odd directed circuit

What is the fastest algorithm for multiplication of two n-digit numbers?

Formulas for which any equivalent CNF formula has exponential length

Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

Practical applications of disjoint set datastructure

Comparing rational numbers

A tentative satisfiability algorithm

Converting a 2-SAT formula into an implication graph

standard sequential algorithm with polylog runtime?

Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

Is it possible to modify dijkstra algorithm in order to get the longest path?

Is MIN or MAX-True-2-XOR-SAT NP-hard?

CNF Generator for Factoring Problems

Does the performance of matrix multiplication depend on the storage of the array?

Minimal size of contracting a DAG into a new DAG

Metrics and algorithms for complexity of a graph

How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

Does every NP problem have a poly-sized ILP formulation?