User Giorgio Camerani

11

35

votes

3

answers

3k

views

Consequences of Factoring being in P?

Nov 12 '15 at 12:36 Community♦ 1

8

34

votes

2

answers

2k

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.4k

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 '19 at 1:39 Community♦ 1

7

21

votes

5

answers

3k

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

8

19

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.4k

5

16

votes

5

answers

547

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 '19 at 16:39 Community♦ 1

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,161

1

14

votes

2

answers

709

views

Lower bounds on #SAT?

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

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

7

13

votes

2

answers

952

views

Counting solutions of Monotone-2CNF formulas

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

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

5

12

votes

1

answer

897

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,539

4

12

votes

1

answer

1k

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.4k

1

12

votes

1

answer

376

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

757

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,399

10

votes

2

answers

547

views

Amplitude of Random Cubic Graphs

graph-theory co.combinatorics

Dec 19 '11 at 17:23 Community♦ 1

3

10

votes

2

answers

466

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

625

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

519

views

The ODD EVEN DELTA problem

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

Jan 10 '13 at 15:37 Community♦ 1

4

8

votes

2

answers

486

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,813

1

8

votes

1

answer

525

views

Help on the following combinatorial problem?

co.combinatorics

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

3

8

votes

2

answers

3k

views

Monotone-2SAT and Vertex Cover

cc.complexity-theory ds.algorithms sat

Sep 20 '10 at 12:53 Community♦ 1

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 16.1k

1

7

votes

4

answers

983

views

Trees: complexity of counting the number of vertex covers

cc.complexity-theory graph-theory counting-complexity

Jun 20 at 14:02 Osman Ay 1

2

7

votes

1

answer

415

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

385

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

302

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 501

3

7

votes

2

answers

486

views

Using SAT for Computer Vision tasks

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

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

7

votes

1

answer

297

views

Determining Graph Hulls

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

Mar 5 '11 at 12:51 Community♦ 1

7

votes

2

answers

562

views

SAT Solution Space - Definition of Cluster of Solutions

cc.complexity-theory sat

Sep 9 '10 at 14:29 Kaveh 20.9k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

53 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?

Monotone-2SAT and Vertex Cover

Reducing #SAT to #MONOTONE-2SAT

Trees: complexity of counting the number of vertex covers

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

SAT Solution Space - Definition of Cluster of Solutions