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 1 Bountied Hot Week Month

0

votes

0

answers

36

views

Unambiguous Problems and Classes over Reals

cc.complexity-theory complexity-classes computing-over-reals

modified yesterday user3483902 893

7

votes

1

answer

145

views

On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

cc.complexity-theory

modified Oct 15 at 22:13 Andrew Kelley 173

1

vote

1

answer

73

views

Common solutions to 3SAT and 2SAT models comprised of the same variables

cc.complexity-theory sat 2sat

modified Oct 15 at 17:05 Community♦ 1

-2

votes

0

answers

31

views

Arithmetic complexity of exponentiation

cc.complexity-theory

asked Oct 14 at 9:25 Quotenbanane 97

14

votes

2

answers

4k

views

What does 'gadget' mean in NP-hard reduction?

cc.complexity-theory np-hardness terminology reductions

modified Oct 9 at 17:06 Joshua Grochow 33.3k

6

votes

0

answers

121

views

Reference for computing the rank of a matrix in polynomial time

cc.complexity-theory reference-request linear-algebra matrices

modified Oct 7 at 14:50 Emil Jeřábek 12.1k

19

votes

1

answer

1k

views

Has parameterized complexity led to better algorithms?

cc.complexity-theory ds.algorithms complexity-classes time-complexity parameterized-complexity

answered Oct 2 at 11:42 Christian Komusiewicz 1,475

7

votes

1

answer

222

views

Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$

cc.complexity-theory

answered Oct 1 at 19:57 Emil Jeřábek 12.1k

11

votes

2

answers

448

views

Boolean formula balancing in $\mathsf{AC^0}$

cc.complexity-theory ds.algorithms reference-request lo.logic boolean-formulas

modified Oct 1 at 17:26 Emil Jeřábek 12.1k

0

votes

0

answers

108

views

Open problems/Conjunctures in non-uniform complexity if proved would imply P=NP

cc.complexity-theory circuit-complexity

asked Sep 30 at 20:13 user60088 17

2

votes

1

answer

133

views

Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

cc.complexity-theory time-complexity reductions oracles nexp

answered Sep 30 at 11:06 Emil Jeřábek 12.1k

4

votes

0

answers

76

views

Complexity of Encoding a Matroid Flow Problem in a Matrix

cc.complexity-theory ds.algorithms graph-theory linear-algebra max-flow-min-cut

modified Sep 26 at 5:40 Naysh 343

2

votes

0

answers

153

views

Complexity of Edge Coloring Regular Graphs With Large Degrees

cc.complexity-theory graph-algorithms graph-colouring

asked Sep 23 at 19:04 Tacocat 21

4

votes

1

answer

192

views

Proof of $LP$ is in $coNP$ without showing it is in $P$?

cc.complexity-theory linear-programming

modified Sep 23 at 5:51 Yonatan N 1,525

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled