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

8

votes

1

answer

173

views

The theoretical complexity of Go - The state of the art

complexity-classes gt.game-theory complexity

modified Mar 26 at 11:22 Denis 6,182

-2

votes

0

answers

39

views

performance vs complexity given an optimization problem

cc.complexity-theory complexity-classes

asked Mar 18 at 18:26 Deniz Sargun 1

2

votes

0

answers

94

views

Is PP invariant under changing its cut-off from 1/2 to another number?

cc.complexity-theory complexity-classes time-complexity

modified Mar 11 at 17:47 user138901 347

4

votes

1

answer

114

views

Is $L \subset 1NL$ when $L \neq NL$?

cc.complexity-theory complexity-classes turing-machines nondeterminism space-complexity

answered Mar 9 at 10:17 domotorp 12.7k

12

votes

2

answers

772

views

A game on several graphs

cc.complexity-theory complexity-classes gt.game-theory

modified Mar 8 at 2:01 Community♦ 1

0

votes

0

answers

78

views

Are there complexity theory consequences of the collapse NEXP=EXP^NP?

cc.complexity-theory complexity-classes time-complexity

asked Mar 6 at 12:35 user138901 347

-2

votes

0

answers

76

views

How often does an NP-complete language appear in PSPACE?

cc.complexity-theory complexity-classes

asked Mar 1 at 16:14 user138901 347

2

votes

2

answers

162

views

Problem in deterministic time $n^p$ and not lower

cc.complexity-theory complexity-classes time-complexity lower-bounds

modified Feb 10 at 9:57 Michael Wehar 4,064

1

vote

0

answers

18

views

Sorting using comparisons that are not simple mappings of simple comparisons

complexity-classes soft-question time-complexity

asked Feb 9 at 14:53 Dale 101

9

votes

1

answer

148

views

Containment problem of an acyclic NFA in an NFA

complexity-classes automata-theory nfa

modified Feb 2 at 11:23 Hermann Gruber 4,359

9

votes

1

answer

233

views

The power of randomized logspace with two-way access to the random tape

cc.complexity-theory complexity-classes turing-machines randomness

answered Jan 30 at 18:52 William Hoza 1,276

0

votes

0

answers

46

views

Randomized Reduction for Maximization Problem

cc.complexity-theory complexity-classes randomness

asked Jan 19 at 17:14 tc1729 101

2

votes

0

answers

87

views

What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$?

complexity-classes

asked Jan 7 at 15:53 Theodore Payton 21

7

votes

1

answer

437

views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

complexity-classes oracles nexp

modified Jan 2 at 19:01 Community♦ 1

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled