User Giorgio Camerani

11

36

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

2

18

votes

2

answers

827

views

Lower bounds on #SAT?

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

Feb 19 at 1:45 Ryan Williams 25.7k

5

17

votes

5

answers

607

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 1,571

7

13

votes

2

answers

986

views

Counting solutions of Monotone-2CNF formulas

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

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

5

12

votes

1

answer

908

views

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

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

Dec 25 '19 at 16:41 Tayfun Pay 2,549

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

384

views

Measuring the randomness of CNF formulas

cc.complexity-theory sat randomness symmetry

Feb 1 '11 at 23:42 Tegiri Nenashi 616

1

11

votes

3

answers

770

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

548

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

634

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

534

views

The ODD EVEN DELTA problem

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

Jan 10 '13 at 15:37 Community♦ 1

1

9

votes

1

answer

527

views

Help on the following combinatorial problem?

co.combinatorics

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

2

8

votes

1

answer

307

views

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

cc.complexity-theory ds.algorithms sat parameterized-complexity exp-time-algorithms

Dec 1 at 12:10 Giorgio Camerani 6,515

4

8

votes

2

answers

497

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

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

2k

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

1k

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

424

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

398

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

304

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

493

views

Using SAT for Computer Vision tasks

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

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

7

votes

1

answer

300

views

Determining Graph Hulls

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

Mar 5 '11 at 12:51 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

55 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

Lower bounds on #SAT?

Unique $k$-SAT benchmarks

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

0-1 Linear Programming: computing the Optimal Formulation

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

Help on the following combinatorial problem?

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

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

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