User dspyz

10 votes

2 answers

2k views

Is Almost-2-SAT NP-hard?

asked Dec 19, 2013 at 23:55

6 votes

1 answer

390 views

Would an optimal sorting network ever have to swap two numbers the "wrong" way

sorting proofs intuition sorting-network

asked Jun 26, 2014 at 16:40

6 votes

1 answer

226 views

Does the 0-1 principle apply to merge networks?

sorting-network

asked Aug 10, 2014 at 4:26

5 votes

1 answer

466 views

Worst case ratio between minimum clique cover and maximum independent set

co.combinatorics approximation-algorithms graph-colouring set-cover clique

asked Feb 5, 2014 at 17:25

5 votes

1 answer

83 views

Can a normal form term be extensionally equivalent to a term with no WHNF?

lambda-calculus normalization universal-turing-machines

asked Dec 6, 2021 at 6:13

4 votes

1 answer

338 views

Asymptotic complexity of CDCL SAT solver that only selects negative literals

sat

asked Jul 20, 2016 at 1:32

3 votes

1 answer

80 views

Translating pure literal elimination into rup

sat

asked Aug 31, 2020 at 6:08

2 votes

1 answer

947 views

How to approximate minimum clique edge cover

graph-algorithms approximation-algorithms set-cover clique

asked Feb 7, 2013 at 0:43

2 votes

0 answers

190 views

Most general form of SAT which is in P

sat polynomial-time resolution

asked Dec 3, 2013 at 22:02

1 vote

0 answers

72 views

Best Asymptotic Complexity for Persistent Union Find

ds.data-structures time-complexity functional-programming

asked Apr 1, 2016 at 19:28

1 vote

0 answers

45 views

Find all paths between specially paired nodes in a DAG in linear time

time-complexity directed-acyclic-graph 2sat

asked Aug 30, 2020 at 0:06

0 votes

0 answers

35 views

Is having a particular form equivalent to being computable for functions on Church numerals?

computability normalization

asked Jan 17 at 3:22

0 votes

0 answers

198 views

Finding assignment-minimum complete k-partite graph cover

graph-theory graph-algorithms approximation-algorithms set-cover clique

asked Aug 25, 2013 at 18:31

0 votes

3 answers

276 views

Terminology for complete k-partite graph where k is not fixed

graph-theory terminology clique

asked Feb 17, 2014 at 17:34

-2 votes

1 answer

67 views

Assign each biclique to a distinct left

graph-theory

asked Nov 18, 2014 at 10:12

Stack Exchange Network

current community

your communities

more stack exchange communities

15 Questions

Is Almost-2-SAT NP-hard?

Would an optimal sorting network ever have to swap two numbers the "wrong" way

Does the 0-1 principle apply to merge networks?

Worst case ratio between minimum clique cover and maximum independent set

Can a normal form term be extensionally equivalent to a term with no WHNF?

Asymptotic complexity of CDCL SAT solver that only selects negative literals

Translating pure literal elimination into rup

How to approximate minimum clique edge cover

Most general form of SAT which is in P

Best Asymptotic Complexity for Persistent Union Find

Find all paths between specially paired nodes in a DAG in linear time

Is having a particular form equivalent to being computable for functions on Church numerals?

Finding assignment-minimum complete k-partite graph cover

Terminology for complete k-partite graph where k is not fixed

Assign each biclique to a distinct left