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

0

votes

0

answers

21

views

Complexity of approximating a real function using queries

reference-request complexity-classes approximation-algorithms query-complexity computing-over-reals

asked 11 hours ago Erel Segal-Halevi 1,480

8

votes

2

answers

973

views

Isn't it “trivial” to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

complexity-classes reductions np-complete physics statistical-physics

modified Jul 3 at 18:28 0x90 421

-3

votes

0

answers

69

views

Is mathematical proof itself NP-hard?

cc.complexity-theory np-hardness complexity-classes proof-complexity

asked Jun 30 at 16:33 Atsina 103

3

votes

1

answer

132

views

Are all RegExp solvable in O(n)?

complexity-classes regular-expressions

answered Jun 18 at 23:25 Armin 213

22

votes

2

answers

748

views

PPAD and Quantum

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

modified Jun 11 at 17:26 Geoffroy Couteau 738

8

votes

1

answer

301

views

How “hard” is it to maximize a polynomial function subject to linear constraints?

cc.complexity-theory complexity-classes time-complexity linear-programming polynomials

modified May 31 at 10:08 Gamow 5,297

1

vote

1

answer

106

views

Diagonalization arguments for QMA type proof systems

cc.complexity-theory reference-request complexity-classes quantum-computing

modified May 23 at 8:04 AngryLion 21

5

votes

0

answers

115

views

Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

complexity-classes quantum-computing quantum-information

modified May 21 at 0:29 bean 49

1

vote

1

answer

80

views

Constrained Topological Sorting with bounded number of chains

np-hardness complexity-classes topological-graph-theory topological-sorting

modified May 15 at 15:47 a3nm 6,766

4

votes

0

answers

104

views

Why can MIP be restricted to just two provers?

complexity-classes interactive-proofs

modified May 14 at 21:45 Hermann Gruber 4,624

11

votes

2

answers

235

views

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

cc.complexity-theory complexity-classes randomness

modified May 5 at 1:00 Ryan Williams 24.9k

7

votes

1

answer

147

views

Complexity class of efficient streaming algorithms

cc.complexity-theory reference-request complexity-classes space-bounded streaming-algorithms

modified May 3 at 20:36 Community♦ 1

9

votes

1

answer

494

views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

complexity-classes oracles nexp

modified May 1 at 20:00 Community♦ 1

10

votes

1

answer

270

views

The theoretical complexity of Go - The state of the art

complexity-classes gt.game-theory complexity

modified Apr 7 at 10:31 TeamBright 241

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled