Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active 2 Bountied Hot Week Month

1

vote

1

answer

31

views

Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

cc.complexity-theory complexity-classes counting-complexity

modified 1 hour ago Lieuwe Vinkhuijzen 1,362

1

vote

0

answers

162

views

+100

Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

cc.complexity-theory graph-theory sat counting-complexity planar-graphs

modified yesterday Giorgio Camerani 6,349

131

votes

28

answers

20k

views

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate

modified 2 days ago Community♦ 1

-3

votes

0

answers

31

views

How to approach SAT-related reduction/proofs? (Double-SAT)

cc.complexity-theory time-complexity sat

asked 2 days ago SadisticSardines 1

21

votes

3

answers

5k

views

Implications of proving NP=RP on complexity theory

cc.complexity-theory np

modified Aug 9 at 18:30 usul 6,569

26

votes

2

answers

4k

views

What would be the consequences of factoring being NP-complete?

cc.complexity-theory reference-request np-hardness factoring

modified Aug 9 at 14:53 vy32 103

6

votes

0

answers

74

views

Counting on grid graphs

cc.complexity-theory complexity-classes counting-complexity

asked Aug 7 at 21:40 delete000 656

32

votes

5

answers

4k

views

Fast Reduction from RSA to SAT

cc.complexity-theory cr.crypto-security sat reductions factoring

modified Aug 4 at 16:14 GManNickG 103

-3

votes

0

answers

63

views

Relation between Randomized and Distribution complexity

cc.complexity-theory

asked Aug 4 at 4:46 T.... 11k

2

votes

0

answers

47

views

The Edge Cover Equilibrium Problem

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

asked Aug 2 at 11:05 Giorgio Camerani 6,349

2

votes

0

answers

145

views

Why is it difficult for $GCT$ to prove super quadratic lower bound?

cc.complexity-theory lower-bounds

modified Aug 1 at 15:01 VS. 529

22

votes

2

answers

803

views

PPAD and Quantum

cc.complexity-theory complexity-classes quantum-computing cr.crypto-security nash-equilibrium

modified Jul 16 at 21:29 Geoffroy Couteau 748

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled