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

2

votes

1

answer

101

views

What graphs on $\mathbb{N}$ can be encoded as regular languages?

complexity-classes fl.formal-languages pl.programming-languages regular-language regular-expressions

answered Oct 21 at 2:39 isaacg 710

0

votes

0

answers

62

views

Unambiguous Problems and Classes over Reals

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

modified Oct 21 at 1:07 user3483902 893

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

2

votes

1

answer

95

views

Complexity of type inference in the simply typed lambda calculus

complexity-classes typed-lambda-calculus

answered Oct 2 at 7:21 Noam Zeilberger 4,073

1

vote

1

answer

53

views

Rademacher Complexity of the Composition with an Indicator

complexity-classes machine-learning

answered Sep 26 at 18:56 Aryeh 8,544

0

votes

0

answers

41

views

Can a NEXP machine simulate invalid queries to a promise problem oracle?

complexity-classes time-complexity reductions promise-problems

modified Sep 15 at 9:58 user138901 373

22

votes

7

answers

2k

views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

cc.complexity-theory complexity-classes np-complete polynomial-time np-intermediate

modified Sep 14 at 20:49 Mark 688

1

vote

1

answer

68

views

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

cc.complexity-theory complexity-classes counting-complexity

modified Aug 13 at 15:52 Lieuwe Vinkhuijzen 1,442

6

votes

0

answers

81

views

Counting on grid graphs

cc.complexity-theory complexity-classes counting-complexity

asked Aug 7 at 21:40 delete000 656

6

votes

1

answer

130

views

Complexity of approximating a real function using queries

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

modified Jul 20 at 10:30 Aryeh 8,544

22

votes

2

answers

817

views

PPAD and Quantum

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

modified Jul 16 at 21:29 Geoffroy Couteau 738

8

votes

2

answers

982

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 441

3

votes

1

answer

137

views

Are all RegExp solvable in O(n)?

complexity-classes regular-expressions

answered Jun 18 at 23:25 Armin 223

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled