User Giorgio Camerani

11

34

votes

3

answers

3k

views

Consequences of Factoring being in P?

Nov 12 '15 at 12:36 Community♦ 1

6

34

votes

2

answers

1k

views

Consequences of $SAT \in BQP$

cc.complexity-theory complexity-classes quantum-computing conditional-results physics

Apr 19 '11 at 6:43 András Salamon 18.2k

8

26

votes

3

answers

2k

views

Consequences of #P = FP

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel

Jan 28 '12 at 21:56 Community♦ 1

2

21

votes

10

answers

3k

views

#SAT Solver download

ds.algorithms sat software

Sep 25 at 1:39 Lev Reyzin♦ 11.3k

7

21

votes

5

answers

2k

views

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

graph-theory co.combinatorics graph-colouring clique

Jan 20 '13 at 16:42 Community♦ 1

7

18

votes

3

answers

2k

views

Shortest Equivalent CNF Formula

cc.complexity-theory co.combinatorics sat formulas

Jan 25 '12 at 19:57 András Salamon 18.2k

5

16

votes

5

answers

497

views

Unique $k$-SAT benchmarks

sat

Sep 18 '13 at 6:01 Community♦ 1

1

14

votes

4

answers

2k

views

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

cc.complexity-theory graph-theory counting-complexity time-complexity

Feb 24 at 16:39 Hermann Gruber 4,299

14

votes

2

answers

1k

views

0-1 Linear Programming: computing the Optimal Formulation

reference-request co.combinatorics optimization linear-programming convex-optimization

Dec 10 '13 at 4:37 Austin Buchanan 2,151

1

14

votes

2

answers

682

views

Lower bounds on #SAT?

cc.complexity-theory lower-bounds sat counting-complexity

Mar 30 '11 at 1:23 Hsien-Chih Chang 張顯之 7,298

7

13

votes

2

answers

889

views

Counting solutions of Monotone-2CNF formulas

cc.complexity-theory ds.algorithms sat counting-complexity

Oct 12 '10 at 9:32 Colin McQuillan 3,436

5

12

votes

1

answer

862

views

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

cc.complexity-theory graph-theory complexity-classes sat counting-complexity

Dec 25 at 16:41 Tayfun Pay 2,489

4

12

votes

1

answer

840

views

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

cc.complexity-theory complexity-classes conditional-results

May 20 '13 at 12:59 András Salamon 18.2k

1

12

votes

1

answer

353

views

Measuring the randomness of CNF formulas

cc.complexity-theory sat randomness symmetry

Feb 1 '11 at 23:42 Tegiri Nenashi 606

1

11

votes

3

answers

720

views

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

cc.complexity-theory ds.algorithms counting-complexity

Oct 26 '16 at 13:58 Andrew Morgan 1,389

10

votes

2

answers

523

views

Amplitude of Random Cubic Graphs

graph-theory co.combinatorics

Dec 19 '11 at 17:23 Community♦ 1

3

10

votes

2

answers

440

views

Compactly representing the solution set of a SAT instance

cc.complexity-theory ds.algorithms sat counting-complexity

Mar 30 '11 at 12:57 Community♦ 1

3

9

votes

2

answers

589

views

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

cc.complexity-theory sat counting-complexity

Aug 30 '13 at 17:54 Community♦ 1

1

9

votes

2

answers

496

views

The ODD EVEN DELTA problem

ds.algorithms graph-theory graph-algorithms counting-complexity

Jan 10 '13 at 15:37 Community♦ 1

3

8

votes

2

answers

460

views

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

cc.complexity-theory quantum-computing randomness physics

May 17 '15 at 21:07 Gil Kalai 5,693

1

8

votes

1

answer

518

views

Help on the following combinatorial problem?

co.combinatorics

Sep 29 '11 at 7:27 Peter Taylor 1,225

4

8

votes

1

answer

1k

views

Reducing #SAT to #MONOTONE-2SAT

cc.complexity-theory ds.algorithms complexity-classes sat

Sep 13 '10 at 15:02 Tsuyoshi Ito 16k

2

7

votes

1

answer

408

views

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

cc.complexity-theory graph-theory complexity-classes counting-complexity

Dec 29 '15 at 13:37 Community♦ 1

7

votes

1

answer

363

views

Number of edge induced subgraphs with given vertex parity

cc.complexity-theory graph-theory co.combinatorics counting-complexity

May 21 '13 at 23:27 Community♦ 1

1

7

votes

2

answers

298

views

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

cc.complexity-theory graph-theory graph-algorithms counting-complexity

Apr 28 '11 at 20:47 Russell Easterly 491

3

7

votes

2

answers

470

views

Using SAT for Computer Vision tasks

ds.algorithms sat ai.artificial-intel cv.computer-vision

Apr 6 '11 at 12:53 Jukka Suomela 10.7k

7

votes

1

answer

296

views

Determining Graph Hulls

cc.complexity-theory ds.algorithms graph-theory graph-algorithms

Mar 5 '11 at 12:51 Giorgio Camerani 6,277

3

7

votes

2

answers

3k

views

Monotone-2SAT and Vertex Cover

cc.complexity-theory ds.algorithms sat

Sep 20 '10 at 12:53 Community♦ 1

7

votes

2

answers

557

views

SAT Solution Space - Definition of Cluster of Solutions

cc.complexity-theory sat

Sep 9 '10 at 14:29 Kaveh 20.7k

1

6

votes

3

answers

907

views

Trees: complexity of counting the number of vertex covers

cc.complexity-theory graph-theory counting-complexity

Mar 21 '11 at 14:30 András Salamon 18.2k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

49 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

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

0-1 Linear Programming: computing the Optimal Formulation

Lower bounds on #SAT?

Counting solutions of Monotone-2CNF formulas

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

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

Measuring the randomness of CNF formulas

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

Amplitude of Random Cubic Graphs

Compactly representing the solution set of a SAT instance

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

The ODD EVEN DELTA problem

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

Help on the following combinatorial problem?

Reducing #SAT to #MONOTONE-2SAT

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

Number of edge induced subgraphs with given vertex parity

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

Using SAT for Computer Vision tasks

Determining Graph Hulls

Monotone-2SAT and Vertex Cover

SAT Solution Space - Definition of Cluster of Solutions

Trees: complexity of counting the number of vertex covers